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