Knapsack Patterns
Quick reference
| 0/1 Knapsack — full 2D table | O(n × capacity) |
| 0/1 Knapsack — 1D, backward scan | O(n × capacity) |
| Unbounded Knapsack (Coin Change, etc.) | O(n × capacity) |
You're packing a hiking backpack. Every item you could bring has a weight and a "how much you'd miss it" value, and the bag only holds so much weight before your shoulders give out. You want the combination of items that packs the most value in without going over the limit. That's the knapsack problem, and it's the same "remember what you've already solved" idea as every other DP topic so far — just with a budget (capacity) as the second axis instead of a grid coordinate.
The core insight: dp[i][capacity] = the best value achievable using only the first i items, with this much capacity left to spend. For each item, there are exactly two choices — leave it out, in which case dp[i][capacity] is whatever it was without this item (dp[i-1][capacity]), or take it, in which case you gain its value but spend its weight (its value + dp[i-1][capacity - its weight]). dp[i][capacity] is whichever of those two is bigger. That's the entire algorithm; everything below is applying it carefully.
0/1 vs. unbounded — same table, opposite scan direction
# dp[i][capacity] = best value using the first i items, this much capacity left
function knapsack01(items, capacity):
dp = 2D array, (n + 1) x (capacity + 1), all zeros
for i from 1 to n:
for c from 0 to capacity:
dp[i][c] = dp[i - 1][c] // leave item i-1 out
if items[i - 1].weight <= c:
dp[i][c] = max(dp[i][c],
items[i - 1].value + dp[i - 1][c - items[i - 1].weight]) // take it
return dp[n][capacity]0/1 Knapsack — full 2D table
function knapsack01(weights, values, capacity):
n = len(weights)
dp = 2D array, (n + 1) x (capacity + 1), all zeros
for i from 1 to n:
for c from 0 to capacity:
dp[i][c] = dp[i - 1][c] // don't take item i-1
if weights[i - 1] <= c:
dp[i][c] = max(dp[i][c], values[i - 1] + dp[i - 1][c - weights[i - 1]]) // take it
return dp[n][capacity]0/1 Knapsack, space-optimized — 1D, capacity iterated BACKWARDS
function knapsack01(weights, values, capacity):
dp = array of size capacity + 1, all zeros
for i from 0 to len(weights) - 1:
for c from capacity down to weights[i]: // ⚠ backwards, not forwards
dp[c] = max(dp[c], values[i] + dp[c - weights[i]])
return dp[capacity]Unbounded Knapsack (e.g. Coin Change) — capacity iterated FORWARDS
function coinChange(coins, amount):
dp = array of size amount + 1
dp[0] = 0
for c from 1 to amount:
dp[c] = infinity
for c from 1 to amount: // forward — reuse is intentional
for coin in coins:
if coin <= c:
dp[c] = min(dp[c], 1 + dp[c - coin])
return dp[amount] if dp[amount] != infinity else -10/1 knapsack's 2D table costs O(n × capacity) time and space, one entry per (item count, capacity) pair, each filled in O(1). The 1D rolling trick above drops space to O(capacity) — only the previous item's row is ever read. Unbounded knapsack has the identical O(n × capacity) time and space shape; the forward-vs-backward scan changes correctness, not the asymptotic cost.
| Operation | Time | Space | Why |
|---|---|---|---|
| 0/1 Knapsack — full 2D table | O(n × capacity) | O(n × capacity) | One dp[i][c] computed per (item, capacity) pair, O(1) work each. |
| 0/1 Knapsack — 1D, backward scan | O(n × capacity) | O(capacity) | Same number of cells filled; only one row of the table needs to exist at a time because each item's row only ever reads the row before it. |
| Unbounded Knapsack (Coin Change, etc.) | O(n × capacity) | O(capacity) | Same shape as 0/1's 1D version — the forward scan is what allows reuse, not a change in how many cells get touched. |
Iterating capacity forward in the 0/1 space-optimized version
This is the single most important knapsack bug, worth real attention: in the 1D version, dp[c - weight] on the right-hand side needs to still be "last item's" value. Scanning forward means a smaller capacity gets updated first, and a larger capacity's update then reads that already-updated (this item's) value — silently letting the same item get packed twice in one call, turning 0/1 knapsack into unbounded knapsack by accident. The fix is always: 0/1 scans capacity backward.
Confusing 0/1 vs. unbounded iteration direction for the problem actually being solved
The two scan directions are not interchangeable defaults — which one is correct depends entirely on whether the problem allows reusing an item. Partition Equal Subset Sum (each number used once) needs the backward scan; Coin Change (each coin denomination reusable) needs the forward scan. Copy-pasting one pattern onto the other problem produces code that runs fine and returns a plausible-looking wrong answer.
Getting dp[0][*] / dp[*][0] base cases backwards
dp[0][c] = 0 for every c (no items to choose from means zero value, no matter how much room there is) and dp[i][0] = 0 for every i (no room means nothing fits, no matter how many options there are). Swapping which index represents "items used" and which represents "capacity" — or seeding only one of the two zero-rows — produces a table that's correct in one direction and silently wrong in the other.
Trusting greedy instead of knapsack DP
Basic Greedy's own coin-change counterexample applies here directly: 0/1 knapsack is exactly a case where the greedy "take the best ratio first" instinct is provably not optimal. Consider capacity 10 with items (weight 6, value 30) and (weight 5, value 24) and (weight 5, value 24): greedy grabs the weight-6 item first (best ratio, value 5.0) and then only has room for nothing else — total 30. But skipping it for the two weight-5 items gives 48. Greedy locks in a choice it can never undo; knapsack DP considers both options at every step and can't be fooled this way.
Sign in to mark problems done — progress syncs across devices.