Question:
A boat can carry at max a weight of W.
There are N people, with weight w_i.
Once the boat crosses the river it never returns.
We have to tell the no. of different groupings possible of people
Solve for T testcases
Input:
T
N W
w_1, w_2, ... w_N
1 <= T <= 100
1 <= N <= 30
1 <= w_i, W <= 2 * 1e9
NOTE: not choosing any person and just passing the boat is also valid.
Sample:
Can someone please help. Thank you
Since N is very low, try backtracting, For each person there will be 2 possibilities, either he will be on board or he will not.
You can also use backtracking, for each no from 1 to 2^n, the setbits will represent the persons on the boat
No, 2^30 is big number (1073741824) Also there are testcases (*100). This problem looks like DP + Math.
Hmmm, since N is 30 only , can we implement dp using maps like
m[{i,j}] will represent total no of combination we can make of j total weight till ith index from left?
Still doesn't work since if the people have weights $$$1, 2, 4, 8,\dots, 2^{29}$$$, all possibe sums below $$$2^{30}$$$ are possible and we would have $$$O(2^{30})$$$ dp states which is too slow.
The problem can be solved using the meet-in-the-middle technique.
Meet in the middle
Yeah, seems like $$$O(2^{\frac n2}\cdot n\cdot T)$$$
What is the limit of W?
Yeah sorry, forgot to add earlier.