DPDynamic Programming
0/1 Knapsack
Choose a subset of items, each used at most once, maximizing total value without exceeding a weight capacity.
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | |
|---|---|---|---|---|---|---|---|---|
| ∅ | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| w1 v1 | · | · | · | · | · | · | · | · |
| w3 v4 | · | · | · | · | · | · | · | · |
| w4 v5 | · | · | · | · | · | · | · | · |
| w5 v7 | · | · | · | · | · | · | · | · |
1/39Row 0 means "no items considered": the best value is 0 for every capacity.
Cell being filledDependency readBase caseComputedReconstructed choice
PseudocodeLearn 0/1 Knapsack →
1dp[0][*] = 02for i in 1 .. n:3 for c in 0 .. W:4 dp[i][c] = dp[i-1][c] // skip item i5 if w[i] <= c:6 dp[i][c] = max(dp[i][c], dp[i-1][c-w[i]] + v[i]) // take7traceback from dp[n][W]Variables
n4
W7
Complexity
best O(n·W)
avg O(n·W)
worst O(n·W)
space O(W)
Speed