Sign in to watch this lesson
Algorithms - Dynamic Programming · 4:36
Knapsack
Each item exists once and has a weight and a value: with items (3, 4) and (4, 5) and a bag of capacity 7, the table f[i][j] = max(f[i-1][j], f[i-1][j-w] + v) reaches 9. We squeeze it into one row and watch the loop direction decide the problem: sweeping j downward reads only the old row (0/1 knapsack), while the same line sweeping upward reads freshly updated cells and takes an item twice (unbounded knapsack). Then bounded knapsack by binary splitting (13 copies become bundles 1, 2, 4, 6; about 40 times faster than copy by copy on this Mac), exact-capacity initialisation, subset sum with bitset shifts, value-indexed tables for huge capacities, and the capital-allocation framing used in quant interviews.
You will learn
- Write the 0/1 knapsack recurrence f[i][j] = max(f[i-1][j], f[i-1][j-w_i] + v_i) and estimate its O(nW) time and memory.
- Compress the table to one row and explain why j must decrease for 0/1 knapsack and increase for unbounded knapsack (the invariant: right of j is the new layer, left of j is still the old one).
- Solve bounded knapsack by binary splitting into bundles 1, 2, 4, ..., remainder in O(W * sum log k_i), and show every count 0..k is reachable.
- Adapt the loop to exact-capacity, subset-sum (bitset) and value-indexed variants, and recognise knapsack as capital allocation with indivisible lots.