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