0/1 knapsack

The problem it solves

You have a fixed budget — kilograms in a bag, megabytes of cache, hours in a sprint — and a set of candidates, each with a cost and a value. Take a subset that fits the budget and maximises total value, where each candidate is taken whole or not at all. That last clause is the “0/1”: no fractions, no repeats. Half of practical optimisation is this problem wearing a costume — feature selection under a size budget, ad slots under a latency budget, cargo, coupons, project portfolios.

The obvious instinct — take things in order of value per kilogram — has a counterexample within arm’s reach: a 9kg treasure worth $95 against three small items of better density that together waste capacity. Fractional knapsack (where you may take part of an item) is provably solved by that greedy; the 0/1 version is NP-hard, and the density heuristic can be made arbitrarily bad. What rescues practice is that hardness is measured against the bit length of the capacity: for integer capacities of ordinary size, a dynamic-programming table solves it exactly in O(n·W). Understanding precisely how those two facts coexist — NP-hard yet routinely solved — is one of the most transferable lessons in the catalogue.

The intuition — and where it breaks down

Stand in front of the last item and ask the only question available: in or out? If it is out, the best packing is whatever the remaining items achieve with the full capacity. If it is in, you bank its value and the remaining items must fit in the capacity minus its weight. You cannot know which branch wins without trying both — so try both, and note that both branches are the same problem with fewer items: a recursion begging for a table.

The table gives the recursion coordinates. Rows are “the first i items considered”; columns are capacities 0..W; a cell holds the best value achievable within that capacity using only those items. Each cell is one in-or-out verdict resolved by two lookups: leave — copy the cell directly above; take — jump to the row above at capacity minus the item’s weight, and add the item’s value. The visualization draws exactly these two reads per cell, and the up-left diagonal of the take branch is the shape to burn in: up because the item is now spent, left because capacity is.

Where intuition misleads: people want the take branch to read the same row — “best at the smaller capacity, plus this item”. But the same row already includes this item in its optimum, so reading it allows packing the item twice; that recurrence is the unbounded knapsack (legitimate, different). The row above means “solutions guaranteed not to contain me”, which is what single-use requires. One row of difference, two different problems.

Loading…

A walkthrough you can check

Items: tent (5kg, $40), stove (4kg, $30), food (6kg, $50), rope (3kg, $10). Capacity 10kg.

1. Tent row: below 5kg, nothing fits — $0. From 5kg up, $40.
2. Stove row, capacity 9: leave keeps $40; take pays 4kg, leaving 5kg for the tent row — $40 + $30 = $70.
3. Food row, capacity 10: leave keeps $70 (tent+stove at 9 ≤ 10). Take pays 6kg, leaving 4kg in the stove row — $30 + $50 = $80. Cell takes $80.
4. Rope row, capacity 10: leave keeps $80; take pays 3kg, leaving 7kg in the food row ($50 + at 7kg… $30+$50 does not fit in 7, best is $50) → $10 + $50 = $60. Keeps $80.

Answer: $80 = stove + food (10kg exactly), and the ending walk lights those two rows. Density order would have started with the tent ($8/kg beats food’s $8.33/kg? — food wins; then tent does not fit with it… try it) — the point of doing one walkthrough by hand is discovering that density order requires luck, while the table requires only arithmetic.

The invariant

dp[i][c] is the maximum value achievable using a subset of the first i items with total weight ≤ c. Induction in fill order: row 0 is all zeros (no items, no value). For any later cell, partition all valid subsets of the first i items by whether they contain item i. Those that do not are exactly the subsets measured by the cell above. Those that do all pay weight w and value v, and what remains of them is exactly a subset of the first i−1 items within c−w — the up-left cell. Two exhaustive, disjoint classes; the max over their two best representatives is the best overall. No other cell layout is consulted, which is why the fill order (rows top-down, any column order within a row) is valid: every read points to an earlier row.

The invariant also explains reconstruction: if dp[i][c] ≠ dp[i−1][c], the optimum must contain item i (the not-contain class capped out lower), so emit it and jump up-left; else go up. The player runs this walk as the closing wash.

Complexity, derived

(n+1)·(W+1) cells, O(1) each: O(n·W) time, O(n·W) space, or O(W) space with a single row swept right-to-left (the direction matters — see below). For n = 100 items and W = 10,000, a million cells: instant.

And yet the problem is NP-hard. Both are true because W enters the running time by magnitude while entering the input by bit length: O(n·W) is pseudo-polynomial, exponential in log W. Blow the capacity up to 2⁶⁴ and the table is unbuildable, which is exactly the regime where knapsack’s hardness has teeth (cryptosystems were built on it). The practical decision procedure: integer capacity of ordinary size → table; huge or fractional capacity → branch-and-bound, approximation (an FPTAS exists), or a different model. Saying “NP-hard” and “solvable in O(n·W)” in the same breath, with the reconciliation, is the strongest three seconds available in this interview.

What people get wrong

• Density greedy: correct for the fractional variant, unboundedly wrong for 0/1. If an interviewer asks “why not sort by value/weight?”, the answer is a two-item counterexample, not a shrug.
• Take-branch on the same row — silently solves unbounded knapsack. The single most common written bug.
• 1D rolling array swept forward: same bug in disguise. The forward sweep lets a cell read an already-updated smaller capacity — this row, item reused. Right-to-left preserves the previous row’s values exactly where the take branch needs them.
• “Exactly W” vs “at most W”: the standard table answers at most. Exact-fill needs −∞ initialisation everywhere except dp[0][0], so infeasible cells cannot pretend to be worth zero.
• Reconstruction from a value tie: comparing dp[i][c] to dp[i−1][c] identifies membership only if you accept any one optimum; when values tie across different subsets, the walk picks one canonical answer — fine, unless the interviewer asked for all of them.

Implementation notes

Production shape: one array dp[0..W], items outer, capacities inner descending: for c from W down to w: dp[c] = max(dp[c], dp[c−w] + v). Eight lines, O(W) memory, and the descending loop is the 0/1 constraint — flip it ascending and you have unbounded knapsack, which is occasionally what you want and should always be what you chose.

Subset-sum is this table with values equal to weights (or booleans with OR); partition-equal-subset is subset-sum to half the total. Recognising these reductions converts three interview problems into one memorised loop. For counting solutions, swap max for sum. For the FPTAS, scale values down by a factor tied to ε and run the value-indexed dual table — worth naming, rarely worth coding live.

Watch overflow in value sums (64-bit accumulators), and note the table visualization’s row labels carry each item’s weight and value precisely so the up-left jump can be checked visually: the take-arrow always lands weight columns left, one row up — if it ever does not, the code is wrong.

The follow-up questions

Why does the take branch read the row above? Because “row above” means “solutions that cannot contain this item”, making take-it-once safe. Same-row reads permit reuse — the unbounded variant. One row encodes the entire 0/1 constraint.

Is O(n·W) polynomial? Pseudo-polynomial: polynomial in the magnitude of W, exponential in its bit length. NP-hardness and practical solvability coexist without contradiction.

How do you recover the packed items? Walk from (n, W): value change versus the row above means the item is in — emit and jump up-left by its weight; unchanged means out — go up. O(n) after the table.

What if items can be reused? What if weights are huge but values small? Reuse: same-row take branch (or ascending 1D sweep) — unbounded knapsack. Huge W, small total value V: run the dual table indexed by value — dp[v] = minimum weight achieving value v — in O(n·V), then answer the largest v with dp[v] ≤ W. Choosing which quantity to index the table by is the general trick worth stating.