Why is there a 1-D array constructed in case of unbounded knapsack and 2-D array constructed in case of 0/1 knapsack?

Question

I saw that a 1-D array is constructed in case of unbounded knapsack and a 2-D array is constructed in case of 0/1 knapsack? Why does this happen? This question is asked in reference to dynamic programming.

Answer 1

Dynamic Progrmamming works by maintaining "states", ofcourse you'd want to represent a state using minimal variables.

Now, These two problems differ in that fact that you can pick single item as many times as you want in Unbounded knapsack problem, However, In 0-1 knapsack problem, you can pick a item only once. This means, I would want to include whether i already picked a item from list in 0-1 Knapsack problem but there's no need to do so in 0-1 knapsack problem. This is exactly the reason for 2nd dimension in 0-1 Knapsack problem.

See, DP of 0-1 Knapsack : dp[i][w] = max(val[i] + dp[i-1][w-wt[i]], K[i-1][w]); . This represent either pick item i and get best solution for items i-1 with weight w - wt[i] , which makes sure we don't pick item i more than once.

See DP of Unbounded Knapsack: dp[w] = max(dp[w], dp[w - wt[i] ] + val[i] ) . There's no need to remember whether we have picked ith item before, we could just reuse it, if it gives us maximum value.