Rating changes for last rounds are temporarily rolled back. They will be returned soon. ×

Misa-Misa's blog

By Misa-Misa, history, 4 months ago,

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.

Test Case

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

$ANS$ = 2

• +9

 » 4 months ago, # |   0 Why it seems like a modified knapsack problem to me XD
 » 4 months ago, # |   0 you can solve this problem with dp bitmask if n <= 20 ))
 » 4 months ago, # |   +11 You can see solution in handbook on page 103
•  » » 4 months ago, # ^ |   +8 Same problem, wtf! Thanks sir.
 » 4 months ago, # |   +3 This is standard subset dp(bitmask dp)for (int s = 1; s < (1<
 » 4 months ago, # |   0 Isn't it knapsack problem?
•  » » 4 months ago, # ^ |   0 yeah, i think it could be solved dp on mask to generate all possible solution to perform the DP more than one time
 » 4 months ago, # |   0