4.60/1 knapsack and matrix-chain multiplication
The idea
0/1 knapsack and matrix-chain multiplication are the two other DPs you must be able to run by hand.
Think of it like this: Packing a bag under a weight limit; choosing where to put brackets so the multiplications are cheapest.
Why it exists
Both appear as table-filling or complexity questions; knapsack also tests "pseudo-polynomial".
How it works
- Knapsack: t[i][c] = max(skip item i, take item i if it fits).
- Time O(nW), which is pseudo-polynomial.
- Matrix chain: m[i][j] = min over k of m[i][k] + m[k + 1][j] + p[i − 1]p[k]p[j].
- Time O(n³), space O(n²); multiplying p×q by q×r costs pqr.
Worked example: Matrix dimensions 40 20 30 10 30
The best parenthesisation is ((A1(A2 A3))A4) with 26000 scalar multiplications.
Now play with it
- →Fill the knapsack table (weights 1 3 4 5, values 1 4 5 7, capacity 7): answer 9.
- →Switch to the chain and watch lengths 2, 3, 4 get filled.
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | |
|---|---|---|---|---|---|---|---|---|
| 0 items | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| item 1 (w1, v1) | · | · | · | · | · | · | · | · |
| item 2 (w3, v4) | · | · | · | · | · | · | · | · |
| item 3 (w4, v5) | · | · | · | · | · | · | · | · |
| item 4 (w5, v7) | · | · | · | · | · | · | · | · |
- item 1, capacity 0: max(skip = 0, take = not allowed) = 0
- item 1, capacity 1: max(skip = 0, take = 1) = 1
- item 1, capacity 2: max(skip = 0, take = 1) = 1
- item 1, capacity 3: max(skip = 0, take = 1) = 1
- item 1, capacity 4: max(skip = 0, take = 1) = 1
- item 1, capacity 5: max(skip = 0, take = 1) = 1
- item 1, capacity 6: max(skip = 0, take = 1) = 1
- item 1, capacity 7: max(skip = 0, take = 1) = 1
- item 2, capacity 0: max(skip = 0, take = not allowed) = 0
- item 2, capacity 1: max(skip = 1, take = not allowed) = 1
- item 2, capacity 2: max(skip = 1, take = not allowed) = 1
- item 2, capacity 3: max(skip = 1, take = 4) = 4
- item 2, capacity 4: max(skip = 1, take = 5) = 5
- item 2, capacity 5: max(skip = 1, take = 5) = 5
- item 2, capacity 6: max(skip = 1, take = 5) = 5
- item 2, capacity 7: max(skip = 1, take = 5) = 5
- item 3, capacity 0: max(skip = 0, take = not allowed) = 0
- item 3, capacity 1: max(skip = 1, take = not allowed) = 1
- item 3, capacity 2: max(skip = 1, take = not allowed) = 1
- item 3, capacity 3: max(skip = 4, take = not allowed) = 4
- item 3, capacity 4: max(skip = 5, take = 5) = 5
- item 3, capacity 5: max(skip = 5, take = 6) = 6
- item 3, capacity 6: max(skip = 5, take = 6) = 6
- item 3, capacity 7: max(skip = 5, take = 9) = 9
- item 4, capacity 0: max(skip = 0, take = not allowed) = 0
- item 4, capacity 1: max(skip = 1, take = not allowed) = 1
- item 4, capacity 2: max(skip = 1, take = not allowed) = 1
- item 4, capacity 3: max(skip = 4, take = not allowed) = 4
- item 4, capacity 4: max(skip = 5, take = not allowed) = 5
- item 4, capacity 5: max(skip = 6, take = 7) = 7
- item 4, capacity 6: max(skip = 6, take = 8) = 8
- item 4, capacity 7: max(skip = 9, take = 8) = 9
Each cell depends only on cells already filled (up, left, diagonal; for the chain, shorter sub-chains), so the work is (number of cells) × (work per cell): O(mn) for LCS and edit distance, O(nW) for knapsack, O(n³) for the matrix chain.
| A1 | A2 | A3 | A4 | ||
|---|---|---|---|---|---|
| · | · | · | · | · | |
| A1 | · | 0 | · | · | · |
| A2 | · | · | 0 | · | · |
| A3 | · | · | · | 0 | · |
| A4 | · | · | · | · | 0 |
- m[1][2] = min over k of m[1][k] + m[k+1][2] + p0·pk·p2; best split after A1, cost 24000
- m[2][3] = min over k of m[2][k] + m[k+1][3] + p1·pk·p3; best split after A2, cost 6000
- m[3][4] = min over k of m[3][k] + m[k+1][4] + p2·pk·p4; best split after A3, cost 9000
- m[1][3] = min over k of m[1][k] + m[k+1][3] + p0·pk·p3; best split after A1, cost 14000
- m[2][4] = min over k of m[2][k] + m[k+1][4] + p1·pk·p4; best split after A3, cost 12000
- m[1][4] = min over k of m[1][k] + m[k+1][4] + p0·pk·p4; best split after A3, cost 26000
Each cell depends only on cells already filled (up, left, diagonal; for the chain, shorter sub-chains), so the work is (number of cells) × (work per cell): O(mn) for LCS and edit distance, O(nW) for knapsack, O(n³) for the matrix chain.
Check yourself
Matrix-chain multiplication of n matrices by DP takes
Exam notes (the dense version)
0/1 knapsack: t[i][c] = max(t[i − 1][c], t[i − 1][c − wᵢ] + vᵢ), O(nW) time, which is pseudo-polynomial (not polynomial in the input size). Matrix chain: m[i][j] = min over k of m[i][k] + m[k + 1][j] + p[i − 1]·p[k]·p[j], O(n³) time and O(n²) space. The order of multiplication changes the cost, not the result.
Previous year questions: Algorithm Design: Divide & Conquer, Greedy, DP (7)
PYQs are grouped by topic, so this is the full set for Algorithm Design: Divide & Conquer, Greedy, DP; try the ones that match this subtopic. Open all 7 on the topic page.