Unbounded Knapsack and Coin Change II
Allow items to be reused by iterating capacity forwards, and solve coin-change-II (count ways) and rod-cutting using this variant.
Unbounded Knapsack Concept
In Unbounded Knapsack, each item can be taken any number of times (unlike 0/1 knapsack where each item is used at most once). The state definition is the same — dp[c] = maximum value achievable with capacity c — but the iteration direction changes. Because items are reusable, when we update dp[c] we want to allow the current item to be used again, so we iterate capacity left to right (forward).
Forward Iteration Enables Reuse
Recall that in 0/1 knapsack we iterated right to left to prevent reuse. In unbounded knapsack we do the opposite: iterate left to right. When computing dp[c], dp[c-w] has already been updated in the current pass — meaning item i was possibly already included. This is exactly what we want: item i can be added again to a solution that already contains item i.
def unbounded_knapsack(weights, values, W):
dp = [0] * (W + 1)
for i in range(len(weights)):
w, v = weights[i], values[i]
for c in range(w, W + 1): # iterate LEFT TO RIGHT
dp[c] = max(dp[c], dp[c - w] + v)
return dp[W]
weights = [1, 3, 4, 5]
values = [1, 4, 5, 7]
print(unbounded_knapsack(weights, values, 7)) # 9All lessons in this course
- 0/1 Knapsack and Space Optimisation
- Unbounded Knapsack and Coin Change II
- Partition Equal Subset Sum
- Target Sum with Positive and Negative Signs