Knapsack Family
Intermediate · 22 min read · Problem-Solving Patterns, Dynamic Programming
Take it or leave it: subset sum, coin change and their variants.
"Can you split this array into two equal-sum halves?" "Fewest coins to make 37?" "How many ways to assign + and − to reach a target?" These look unrelated, but they're all the knapsack family: a set of items, a budget (capacity, amount, target), and for each item a choice — take it or leave it (or take it again).
The classic 0/1 knapsack
State: dp[i][c] = best value using the first i items with capacity c. Choice for item i: skip it, or take it if it fits.
The one-line rule
Memorise this table. It's the difference between correct and subtly wrong in every problem below.
0/1 problems
Equivalent to: is there a subset summing to total / 2? A boolean knapsack:
Unbounded problems
Coins can be reused, so loop upward. For each amount, try each coin as the last coin:
Choosing the template
Practice ladder
Interview questions
- In the one-dimensional 0/1 knapsack, why must the capacity loop run downward?
- Why does greedy fail for the coin change problem?
Further reading
Key takeaways
- Knapsack = items + budget + take/skip. Table indexed by the budget.
- 0/1 (each once) → loop capacity downward; unbounded (reuse) → upward.
- Counting combinations: items in the outer loop; swapped loops count ordered sequences.
- Rewrite problems into knapsack form (target sum: P = (total + target) / 2).
- Use amount + 1 as infinity; greedy coin change can be wrong.