Misa-Misa's blog

An Interview Problem
By Misa-Misa, history, 6 months ago, In English

Past week, i was asked this problem in an interview, i don't know the solution till now, help me with this.

Problem

There are $$$N$$$ people in a group, weight of $$$i$$$ 'th person is $$$W[i]$$$, there is a lift of capacity $$$C$$$ which is the maximum weight the lift can carry, everyone wants to go to the top floor via lift.
Determine $$$M$$$, where $$$M$$$ is the minimum times lift must be used by the group so that everyone is able to go to the top floor.

Constraints

Not sure about constraints, please give the best solution you can.

Test Case

$$$N$$$ = 4
$$$C$$$ = 90
$$$W$$$ = [10, 20, 70, 80]

$$$ANS$$$ = 2

  • Vote: I like it
  • +9
  • Vote: I do not like it

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Why it seems like a modified knapsack problem to me XD

→ Reply
»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

you can solve this problem with dp bitmask if n <= 20 ))

→ Reply
»
6 months ago, # |
  Vote: I like it +11 Vote: I do not like it

You can see solution in handbook on page 103

→ Reply
»
6 months ago, # |
  Vote: I like it +3 Vote: I do not like it

This is standard subset dp(bitmask dp)

for (int s = 1; s < (1<<n); s++) {

// initial value: n+1 rides are needed

best[s] = {n+1,0};

for (int p = 0; p < n; p++) {

if (s&(1<<p)) {

auto option = best [s^(1<<p)];

if (option.second+weight[p] <= x) {

// add p to an existing ride option.second += weight[p];

} else {

// reserve a new ride for p option.first++;

option.second = weight[p];

}

best[s] = min(best[s], option);

} } }

→ Reply
»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Isn't it knapsack problem?

→ Reply
  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    yeah, i think it could be solved dp on mask to generate all possible solution to perform the DP more than one time

    → Reply
»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

link

→ Reply