0/1 Knapsack
0/1 Knapsack: given item weights and values and a knapsack capacity, maximise the total value carried. Each item may be taken at most once.
- 1 <= n <= 10³
- 1 <= W <= 10³
- 1 <= value[i], weight[i] <= 10³
- Each item may be taken at most once
Intuition
The 0 1 knapsack problem gives item weights and values plus a capacity, and asks for the maximum value you can carry, taking each item at most once. That last restriction is the whole difficulty.
The natural first instinct is greedy by value-to-weight ratio, and it is wrong here. It works for the fractional version, where you can take part of an item and fill the sack exactly. With indivisible items the capacity must be packed as a whole, and an item with a slightly worse ratio may fit the remaining space perfectly where the better one leaves a gap.
So every item poses one binary question — take it or skip it — and both branches have to be explored. Skipping leaves the capacity untouched; taking it consumes weight and earns value:
- dp[i][c] = max(dp[i−1][c], value[i] + dp[i−1][c − weight[i]])
The detail that enforces "at most once" is that both branches read row i−1, never row i. An item can never consult a state that already includes itself, so it cannot be taken twice.
That is also what dictates the space optimisation. Collapsing to one row works, but the inner loop must run backwards over capacity — iterating forward would let dp[c − weight] already include the current item, silently turning this into unbounded knapsack. Rod cutting is that other problem, and the two differ by loop direction alone.
The template every take-or-skip DP is built from. Each item is used at most once, so the state is (items considered, capacity remaining) and each cell picks the better of two options. Recognising the 0/1 shape — indivisible items, one use each — is what tells you greedy will fail and a table is required. It is the same reason the 0/1 knapsack problem using greedy method is taught as a counterexample rather than a solution, and why exact alternatives like the 0/1 knapsack problem using branch and bound prune the search tree instead of pretending a ratio ordering is optimal. Courses that set it as the 0/1 knapsack problem in daa use exactly this contrast.
Approach
Before reading on: price up what the direct approach costs here, then ask what a single cell should mean, and which earlier cells it needs. Aim for O(n · capacity) time and O(n · capacity) space.
See why greedy fails
Value-to-weight ratio is optimal for fractional knapsack but not here. Indivisible items mean capacity must be packed exactly, so a worse-ratio item that fits the remaining gap can beat a better one that leaves it empty.
Define the two-dimensional state
dp[i][c] is the best value using only the first i items within capacity c. Row 0 is all zeros — with no items available, no value is achievable at any capacity.
Take the better of skip and take
Skipping gives dp[i-1][c]. Taking gives value[i] + dp[i-1][c - weight[i]], but only when the item fits. If it does not fit, skipping is the only option and no maximum is taken.
Understand why both branches read the previous row
Neither branch consults row i, so an item can never be counted twice. This is exactly what enforces the at-most-once rule — the structure of the recurrence, not a separate check.
Collapse to one row carefully
A single array over capacity suffices, but the inner loop must run backwards. Iterating forward lets dp[c - weight] already include the current item, which silently converts the problem into unbounded knapsack.
Contrast with unbounded knapsack
Rod cutting and coin change allow unlimited copies and sweep the capacity forward for exactly that reason. The two problems differ by loop direction alone, which is why copying the wrong template is such a common error.
Cost of the tabulation
Every one of the n × capacity cells is computed once, giving O(n · capacity) time with O(capacity) space after the rolling-array optimisation. This is pseudo-polynomial — it scales with the numeric capacity, not the input size.
Solution & live demo
Common pitfalls
Sorting by value-to-weight ratio and taking greedily
items.sort(key=lambda x: x[0] / x[1], reverse=True)
for v, w in items:
if cap >= w: total += v; cap -= wdp[i][c] = max(skip, take)
That's the fractional knapsack solution, and it fails here: with capacity 4 and items (value 3, weight 3) and (value 4, weight 4), the better ratio takes the 3 and wastes a unit. Indivisible items break the exchange argument that makes greedy safe.
Indexing weights with the table index
if wt[i] <= c:
take = val[i] + dp[i - 1][c - wt[i]]if wt[i - 1] <= c:
take = val[i - 1] + dp[i - 1][c - wt[i - 1]]Row i means "the first i items", so the item it just added sits at array position i - 1. Using i directly reads the next item and runs off the end on the last row.
Considering take when the item doesn't fit
take = val[i-1] + dp[i-1][c - wt[i-1]] dp[i][c] = max(skip, take)
if wt[i - 1] <= c:
dp[i][c] = max(skip, take)
else:
dp[i][c] = skipA negative capacity index wraps to the far end of the row in Python, silently mixing in a value from an unrelated state. An item heavier than the remaining capacity has exactly one option — skip.
Edge cases
Column 0 stays 0 — nothing fits, so no value is achievable.
weight > c in every column, so the value is inherited unchanged from the row above.
Every take branch wins and the answer is the sum of all values.