lecxe's blog

Any ideas for this question?
By lecxe, 15 months ago, In English

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

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

Comments Comments (9)
| Write comment?
»
15 months ago, # |
  Vote: I like it -10 Vote: I do not like it

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.

→ Reply
»
15 months ago, # |
  Vote: I like it -10 Vote: I do not like it

You can also use backtracking, for each no from 1 to 2^n, the setbits will represent the persons on the boat

→ Reply
  • »
    »
    15 months ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    No, 2^30 is big number (1073741824) Also there are testcases (*100). This problem looks like DP + Math.

    → Reply
    • »
      »
      »
      15 months ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      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?

      → Reply
      • »
        »
        »
        »
        15 months ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        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.

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

Meet in the middle

→ Reply
  • »
    »
    15 months ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    Yeah, seems like $$$O(2^{\frac n2}\cdot n\cdot T)$$$

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

What is the limit of W?

→ Reply
  • »
    »
    15 months ago, # ^ |
    ← Rev. 2   Vote: I like it +1 Vote: I do not like it

    Yeah sorry, forgot to add earlier. 

    1 <= w_i, W <= 2*1e9
    → Reply