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
Why it seems like a modified knapsack problem to me XD
you can solve this problem with dp bitmask if n <= 20 ))
You can see solution in handbook on page 103
Same problem, wtf! Thanks sir.
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);
} } }
Isn't it knapsack problem?
yeah, i think it could be solved dp on mask to generate all possible solution to perform the DP more than one time
link