Help in Space Reduction in Knapsack, using Top-Down Approach.

Revision en1, by B0JACK, 2020-02-01 21:42:10

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.

Tags topdown, dp, 0/1 knapsack, iamstupid

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English B0JACK 2020-02-01 21:42:10 990 Initial revision (published)