Unbounded Knapsack Problem: How Is It Different?
Learn the unbounded knapsack problem, how it differs from 0/1 knapsack, its DP recurrence, and a working Python solution.
Expected Interview Answer
The unbounded knapsack problem allows each item type to be picked an unlimited number of times, so the DP recurrence becomes dp[w] = max(dp[w], value[i] + dp[w-weight[i]]) iterated with capacity increasing left to right, since reusing dp[w-weight[i]] within the same pass is exactly what allows repeated selection.
Unlike 0/1 knapsack, there is no notion of 'items remaining' to track, because an item can be reselected as many times as capacity allows, so a single 1D array indexed by capacity is sufficient and there is no need for a 2D item-by-capacity table. The key implementation difference from 0/1 knapsack is the loop direction: iterating capacity from low to high lets dp[cap - weight[i]] already include the current item, enabling reuse, whereas 0/1 knapsack must iterate high to low to prevent it. This variant models problems like rod cutting, minimum coins to make change, and unlimited supply resource allocation. Time complexity stays O(n*W), the same order as 0/1 knapsack, but the space is naturally O(W) without needing the reverse-iteration trick.
- Naturally O(W) space with a single forward pass array
- Models unlimited-supply resource problems directly
- Same O(n*W) time as 0/1 knapsack, simpler loop structure
- Directly generalizes to coin change and rod cutting
AI Mentor Explanation
A groundskeeper stocking a fixed-size storage shed with sandbags of a few standard weights, where the supplier has unlimited stock of each weight, can grab the same weight of sandbag as many times as the remaining space allows. Filling the shed's capacity table left to right, from empty up to full, means each capacity level can reuse a sandbag weight chosen at a smaller capacity level within the same pass. This is different from picking unique rare trophies where each one is used at most once. Because supply is unlimited, the forward-filling table naturally allows the same weight to appear multiple times in the optimal stacking.
Step-by-Step Explanation
Step 1
Define the state
dp[w] = max value achievable with capacity w, allowing each item type to repeat.
Step 2
Write the recurrence
dp[w] = max(dp[w], value[i] + dp[w-weight[i]]) for every item i whose weight[i] <= w.
Step 3
Iterate capacity low to high
Fill dp forward so dp[w-weight[i]] can already include the current item, enabling reuse.
Step 4
Compare against 0/1 knapsack
Only the loop direction differs; the state itself needs no per-item dimension since items are reusable.
What Interviewer Expects
- Identify that items can be reused unlimited times
- State the loop direction (forward) and explain why it enables reuse
- Contrast this precisely against 0/1 knapsack's reverse iteration
- Connect it to coin change / rod cutting as concrete applications
Common Mistakes
- Iterating capacity high-to-low out of habit from 0/1 knapsack, which blocks reuse
- Adding an unnecessary item dimension to the DP table
- Assuming the recurrence formula itself differs from 0/1 knapsack (only the loop order differs)
- Not recognizing coin change as an unbounded knapsack variant
Best Answer (HR Friendly)
“Unbounded knapsack is the same idea as regular knapsack, maximizing value within a capacity, except now I can reuse the same item as many times as I want. The trick to implementing it is filling the DP array from low capacity to high capacity in a single forward pass, so an item picked for a smaller capacity is available to be picked again for a larger one.”
Code Example
def knapsack_unbounded(weights, values, capacity):
dp = [0] * (capacity + 1)
for cap in range(1, capacity + 1):
for i in range(len(weights)):
if weights[i] <= cap:
dp[cap] = max(dp[cap], values[i] + dp[cap - weights[i]])
return dp[capacity]
weights = [2, 3, 5]
values = [3, 5, 8]
print(knapsack_unbounded(weights, values, 8)) # 13 (three items of weight 3 + one of weight... best combo)Follow-up Questions
- How does rod cutting map onto unbounded knapsack?
- How would you modify this to also track which items were chosen?
- Why does the loop-order change alone flip 0/1 into unbounded behavior?
- How would you solve this if item weights could be very large (capacity too big for a table)?
MCQ Practice
1. What is the essential loop-order difference between unbounded and 0/1 knapsack in the 1D array solution?
Forward iteration lets a smaller-capacity result that already used the current item feed into a larger-capacity result, enabling reuse.
2. Which classic problem is a direct instance of unbounded knapsack?
Rod cutting picks piece lengths (with unlimited supply of each length) to maximize total value within a fixed rod length, exactly matching unbounded knapsack.
3. Does unbounded knapsack need a per-item dimension in its DP state?
Since items can be reused freely, there is no need to track "items considered so far" — one array over capacity suffices.
Flash Cards
What is the key rule change from 0/1 to unbounded knapsack? — Each item type may be selected an unlimited number of times.
Which loop direction enables item reuse in the 1D array? — Iterating capacity from low to high (forward).
What real problem is unbounded knapsack equivalent to? — Rod cutting (and closely related to coin change).
Does unbounded knapsack need a 2D table? — No — a single 1D array over capacity is sufficient.