Jalboss's blog

By Jalboss, history, 4 years ago, In English

Hello everyone I am stuck on this problem .

  1. Please help me by explaining the dp recurrence and also if this can be solved by dp + bitmask technique.

The dp recurrence looks like this :

Let dp[i][j][k] be the number of ways to choose j numbers among the first i numbers such that the sum becomes k. You can update this array from smaller i, and when i > 0, dp[i][j][k] = dp[i−1][j][k]+dp[i−1][j −1][k−xi]. (Make sure that you don’t access to negative indices). Then, the answer is the sum of dp[N][t][At] for 0 ≤ t ≤ N.

Can somebody explain me this ?

  • Vote: I like it
  • -7
  • Vote: I do not like it

| Write comment?
»
4 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

You can rewrite the problem as such. Find all of these:

  • number of ways to pick 1 card with sum $$$A$$$;
  • number of ways to pick 2 cards with sum $$$2A$$$;
  • number of ways to pick 3 cards with sum $$$3A$$$;
  • ...
  • number of ways to pick $$$k$$$ cards with sum $$$kA$$$;
  • ...

Each of these can be done by doing a completely classical textbook knapsack DP (and the recurrence you wrote is more-or-less exactly that.