B0JACK's blog

Help in Space Reduction in Knapsack, using Top-Down Approach.
By B0JACK, history, 5 years ago, In English

I'm really sorry if this post sounds stupid, but I'm currently struggling in DP and want to tackle every problem in every possible aspect. The question states that we're given a particular capacity weight W, and we have N items, with ith element having v[i] value and w[i] weight, and we want to maximize the total value we can achieve ( Basically a knapsack problem ). Constraints are as follows,

W <= 1e4;
vi <= 1e9;
wi <= 1e4;
N <= 1e4;

This question can be done, in O(N*W) Time and Space complexity using both top-down and bottom-up approach, and I can further reduce the space to O(2*W) and time O(N*W) using bottom-up approach [link to the bottom-up approach : Link], but I'm unable to think of a similar space-reduced top-down approach. Any intuition behind implementing the "state-reduced" top-down approach will be greatly appreciated.

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

»
5 years ago, # |
  Vote: I like it +6 Vote: I do not like it

If you want to reduce space to "O(w*2)" you need to maintain strict order of calculation dp states. First you calculate dp[0][i] (for all i), then dp[1][i], then dp[2][i], etc. That's because dp-formula look like dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]]+v[i]). Calculating dp[1][i] (for all i) requires information about dp[0][j] (for all j), and same for other dp[2][i], dp[3][i], etc. That's the reason why we need only "O(w*2)" space.

When you use recursive approach, you can't maintain that strict order of dp states (just like in bottom-up). So, imo, it's impossible.

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Thank you for your insight, will keep this in mind for future problems.

    → Reply