CONCEPT · Expert
Knapsack
also 0/1 knapsack · unbounded knapsack · coin change
Choose items under a capacity budget to optimize value (or coin count). 0/1 allows each item once; unbounded allows unlimited copies — the rolling-array loop direction is the switch.
Intuition
Capacity is a second index, not a greedy leftover. Each item is a layer: skip the old row, or pay the weight and add the value from a strictly smaller capacity.
When to reach for it
- Maximize value with weight ≤ W, each item at most once (0/1)
- Unlimited coins / unbounded items (walk capacity upward, or complete inner coin loop)
- Min coins to make amount, or count combinations (watch whether order matters)
- W is a few thousand so an O(nW) table fits
Usual pits
- Greedy by density or largest coin — fails on [1,3,4] amount 6
- Inner loop direction: downward is 0/1, upward is unbounded
- Initializing with -∞ when leftover capacity is allowed (use 0 for 'at most W')
- Returning 0 instead of -1 when amount is impossible; amount 0 is 0 coins, not -1
- O(nW) when W is 1e9 — the table does not exist