Module 30
Knapsack DP
Choose items under a capacity: 0/1 and unbounded knapsack, subset sums, coin change, counting combinations vs permutations, and two-dimensional capacities.
Knapsack problems ask which items to pick when there's a limit: a bag's weight, a target sum, an amount of money. The DP state adds the remaining capacity to the item index, and one loop direction decides whether each item can be used once or many times.
This module teaches the 0/1 knapsack table and its one-row version, the unbounded variant, and the family of problems that turn into it: equal partitions, target sums with + and −, splitting stones, coin change (fewest coins and number of ways), and capacities with two dimensions.
Best after: DP Foundations: 1D
Part 1
Learn the ideas
- 30.10/1 Knapsackdp[c] = best value with capacity c using the items seen so far. For each item, loop capacity downwards so the item is used at most once.16 min
- 30.2Subset Sum and Its DisguisesMany problems become "can (or how many ways can) a subset reach sum S?" after a little algebra.12 min
- 30.3Coin Change: Combinations vs PermutationsCoins in the outer loop count combinations (order doesn't matter). Amount in the outer loop counts sequences (order matters).10 min
Part 2
Solve the problems
In order of difficulty. Each one shows the pattern it teaches.
Boolean 0/1 knapsack towards total / 2.
Algebra turns ± signs into counting subsets with sum (total + target) / 2.
Recognising a hidden partition: the result is the difference between two groups.
Unbounded knapsack minimising the number of items.
Counting combinations: coins in the outer loop.
Counting ordered sequences: amount in the outer loop.
Coin change where the coins are 1, 4, 9, 16, …
A knapsack with two capacities at once.