← All Comparisons
0/1 Knapsack vs Unbounded Knapsack
Quick Answer
Use 0/1 Knapsack when each item can be used at most once (subset selection problems). Use Unbounded Knapsack when items can be used unlimited times (coin change, rod cutting). The difference comes down to one line in the recurrence.
Side-by-Side Comparison
| Aspect | 0/1 Knapsack | Unbounded Knapsack |
|---|---|---|
| Item usage | Each item used at most once | Each item can be used unlimited times |
| DP state | dp[i][w] = best using items 0..i with capacity w | dp[w] = best achievable with capacity w |
| Transition (take item i) | dp[i-1][w - wt[i]] + val[i] | dp[i][w - wt[i]] + val[i] |
| 1D optimization loop | Iterate capacity right-to-left | Iterate capacity left-to-right |
| Space (optimized) | O(W) | O(W) |
| Time complexity | O(n * W) | O(n * W) |
| Key signal | "Choose a subset", "each item once" | "Unlimited supply", "coin change", "rod cutting" |
When to Use 0/1 Knapsack
- -You have a set of items and must select a subset that maximizes value without exceeding capacity.
- -The problem is about partitioning — can you divide elements into two groups with equal sum?
- -Target sum with distinct elements — count subsets that sum to a target.
- -Each decision is binary: include or exclude each item exactly once.
When to Use Unbounded Knapsack
- -Items have unlimited supply — you can pick any item as many times as you want.
- -Coin change problems — find the minimum coins or count the number of ways to make a target amount.
- -Rod cutting — cut a rod into pieces to maximize revenue, reusing lengths.
- -The problem says "you have an infinite supply" or "you can use each denomination any number of times."
Key Differences
The one-line difference in the recurrence
In 0/1 Knapsack, when you take item i, you move to dp[i-1] (previous row) because item i is now used up. In Unbounded Knapsack, you stay at dp[i] (same row) because you can take item i again.
Space-optimized loop direction
When using a 1D DP array, 0/1 Knapsack iterates capacity from right to left to avoid using an item twice (each cell reads from values that haven't been updated yet). Unbounded Knapsack iterates left to right so that updated values (which already reflect reusing items) are available.
Code Comparison (1D Space-Optimized)
0/1 Knapsack
dp = [0] * (W + 1)
for i in range(n):
# Right to left!
for w in range(W, wt[i]-1, -1):
dp[w] = max(
dp[w],
dp[w - wt[i]] + val[i]
)Unbounded Knapsack
dp = [0] * (W + 1)
for i in range(n):
# Left to right!
for w in range(wt[i], W + 1):
dp[w] = max(
dp[w],
dp[w - wt[i]] + val[i]
)How to Decide
- Can each item be used only once? 0/1 Knapsack. Keywords: "subset", "partition", "choose from a set."
- Can items be reused? Unbounded Knapsack. Keywords: "unlimited supply", "coin change", "any number of times."
- Is it a partition/subset-sum problem? 0/1 Knapsack with target = totalSum / 2.
- Is it a "number of ways to make amount" problem with reuse? Unbounded Knapsack (coin change variant).
- Does the problem mention "rod cutting" or "ribbon cutting"? Unbounded Knapsack.
Example Problems
0/1 Knapsack
- 1.Partition Equal Subset Sum — Can you split the array into two subsets with equal sum? (target = total / 2)
- 2.Target Sum — Assign + or - to each number to reach a target. Reduces to subset sum.
- 3.Last Stone Weight II — Minimize the last stone weight by optimally smashing pairs. Reduces to minimum subset difference.
Unbounded Knapsack
- 1.Coin Change — Find the minimum number of coins to make a target amount (unlimited coin supply).
- 2.Coin Change II — Count the number of combinations to make a target amount.
- 3.Rod Cutting — Cut a rod of length n into pieces to maximize total revenue, with prices for each length.