educative.io

I can't tell the difference of the code between unbounded question and 0/1 knapback

For 0/1 knapback bottom-up solutions, how can we control that every element is only be used once?

1 Like

For 0/1 knapsack:
dp[i][c] = max (dp[i - 1][c], profit[i] + dp[i - 1][c - weight[i]])
(we look at last row)

For unbounded knapsack:
dp[i][c] = max (dp[i - 1][c], profit[i] + dp[i][c - weight[i]])
(we look at last row and current row)

1 Like