Advanced · Module 18 · Lesson 4
Unbounded knapsack
Reuse choices for coin change and related problems.
Lesson 108 of 123
1d streakUnbounded Knapsack: Infinite Choice Reusability & Forward Loops
In Unbounded Knapsack problems (Coin Change, Rod Cutting, Integer Break), items may be selected an unlimited number of times. The core algorithmic distinction from 0/1 Knapsack lies in loop direction: while 0/1 Knapsack iterates capacity backward to prevent duplicate item use, Unbounded Knapsack deliberately iterates capacity forward from coin to amount, allowing the updated state dp[a - coin] to compound and reflect multiple instances of the same item.
// Coin Change: Minimum coins to make amount
public int coinChange(int[] coins, int amount) {
int max = amount + 1;
int[] dp = new int[amount + 1];
Arrays.fill(dp, max);
dp[0] = 0; // 0 coins needed for amount 0
for (int coin : coins) {
// Forward loop permits reusing the current coin multiple times
for (int a = coin; a <= amount; a++) {
dp[a] = Math.min(dp[a], dp[a - coin] + 1);
}
}
return dp[amount] > amount ? -1 : dp[amount];
}
// Coin Change 2: Total number of combinations
public int change(int amount, int[] coins) {
int[] dp = new int[amount + 1];
dp[0] = 1; // 1 way to make amount 0: empty set
for (int coin : coins) {
for (int a = coin; a <= amount; a++) {
dp[a] += dp[a - coin];
}
}
return dp[amount];
}Active Recall Checkpoint
In Coin Change 2 (total combinations), why must the outer loop iterate over coins and the inner loop iterate over amount, rather than vice versa?
Show answer & explanation
Looping coins on the outside guarantees each coin is processed in a fixed order, counting unique combinations (e.g. [1, 2]). Looping amount on the outside counts ordered permutations (e.g. counting both [1, 2] and [2, 1] as distinct ways).
Use it when
Use Unbounded Knapsack whenever items or denominations can be selected multiple times without supply constraints.
Reconsider when
If each denomination has a strict inventory limit (e.g. at most 3 quarters), use Bounded Knapsack with binary decomposition into 0/1 items.
Cost Model
Complexity & Trade-offs
When to use it
- Optimization, counting, and feasibility with overlapping subproblems.
- Sequence, grid, interval, tree, subset, and digit constraints.
- Replacing exponential recursion with reusable state.
Common mistakes
- Defining a state that lacks information needed by the transition.
- Iterating in an order that reads unresolved or same-round values.
- Optimizing space before proving dependencies.
Practice prompts
- Reproduce the worked Unbounded knapsack example without looking at the trace.
- Change one input condition and explain whether the Unbounded knapsack invariant still holds.
- Implement the approach, derive its cost, and compare it with a straightforward baseline.
Mastery check