0/1 knapsack — every question, written out
Pack a fixed capacity for maximum value, each item taken whole or not at all. The template half of all optimisation DP is cut from, built row by row.
Read the 0/1 knapsack explanation and watch it run
What do the two axes mean, and what does one cell hold?
Invariant identification
Rows are "the first i items considered", columns are capacities, and the cell is the best value achievable
Saying "the first i items" rather than "item i" is what makes the induction work: the two branches partition all valid subsets into those containing item i and those not, and each class is measured by a cell already computed. The cell holds a maximum value, not a decision and not a subset — the decisions are recovered afterwards by walking backwards. Prism labels each row with the item’s weight and value so the up-left jump can be checked against the drawing.
The take branch reads `dp[i-1][c - w]`. Why the row ABOVE and not the same row?
Invariant identification
The row above holds solutions guaranteed not to contain this item, which is what "at most once" requires
Reading the same row would allow the optimum at capacity c−w to already include this item, so adding it again packs the item twice — that recurrence is unbounded knapsack, legitimate and different. One row of difference encodes the entire 0/1 constraint. Prism records both reads for every cell, so you can watch the take branch jump a row up and `weight` columns left.
See it run — Two cells read at once: directly above for leave, and up-left by 5kg for take.
Someone writes the take branch as `dp[i][c - w] + v`. What problem have they solved?
Code diagnosis
Unbounded knapsack — each item can now be packed as many times as it fits
The output is a perfectly correct answer to the wrong problem, which is why this is the most common written bug in the family: the numbers look plausible and are simply too large. Unbounded knapsack is a real variant worth knowing — same table, same-row take branch — so the fix is to be deliberate about which one you meant. If the interviewer asks for "coin change with unlimited coins", this is the recurrence you want.
The table is collapsed to one array and swept `for c from w to W`. What breaks?
Code diagnosis
The sweep reads capacities it has already updated this round, so items get reused
In one dimension, `dp[c - w]` must still hold the PREVIOUS row’s value when the take branch reads it, and only a descending sweep guarantees that. Ascending, it has already been updated with this same item, which reintroduces the same-row bug in disguise. The descending loop IS the 0/1 constraint — flip it and you have unbounded knapsack, which should always be a choice rather than an accident.
What is the running time of the table, in terms of what?
Complexity derivation
O(n · W) — one cell per item and capacity, with two lookups each
The grid is (n+1) by (W+1) and each cell does constant work, so a hundred items against a capacity of ten thousand is about a million cells — instant. Note that W is a NUMBER from the input, not a count of things, which is the observation the next question turns on. Space is the same product, or O(W) with the rolling array swept downward.
Follow-up: 0/1 knapsack is NP-hard, yet you just gave an O(n·W) algorithm. Reconcile that.
Complexity derivation
W enters the running time by magnitude but the input by bit length, so O(n·W) is exponential in the input size
Writing a capacity of 2⁶⁴ takes 64 bits, so an algorithm linear in the capacity is exponential in the length of that number — the definition of pseudo-polynomial. For ordinary integer capacities the table is entirely practical; blow W up and it becomes unbuildable, which is the regime where the hardness has teeth. Saying "NP-hard" and "O(n·W)" in the same breath with this reconciliation is the strongest three seconds available in the interview.
Follow-up: the capacity is enormous but the values are small integers. Now what?
Trade-off & selection
Index the table by value instead — the minimum weight to reach each value — and read off the largest affordable one
Build `dp[v]` = the minimum weight achieving total value exactly v, fill it in O(n·V), then answer with the largest v whose weight fits. The general trick is what to carry away: choose whichever quantity is small to index the table by, and store the other as the value. Recognising that the roles of weight and value can be swapped is worth more than either table on its own.
What is the smallest amount of memory the standard table can run in?
Complexity derivation
O(W) — a single array of capacities, since each row reads only the row above
The dependency pattern is one row back, so a single array swept from W down to w carries everything the fill needs. That is the eight-line production shape, and the descending direction is doing double duty as both the memory saving and the single-use constraint. The cost of collapsing is the same as everywhere in dynamic programming: you lose the provenance the reconstruction walk needs.
The table is full. How do you find out WHICH items were packed?
Trace prediction
From the corner, compare each cell with the one above: different means the item is in, then jump left by its weight
If `dp[i][c]` differs from `dp[i-1][c]`, the not-containing class capped out lower, so the optimum must include item i — emit it and move up-left by its weight; otherwise move straight up. The walk is O(n) after the table and needs nothing extra stored. Prism runs it as the closing wash, lighting the cells that actually packed the bag.
See it run — The backward walk lights the food row at 10kg, then jumps to the stove row at 4kg.
Items a(2kg,$3), b(3kg,$4), c(4kg,$5), d(5kg,$6) with a 12kg bag. What does value-per-kilogram greedy get, and what is optimal?
Trade-off & selection
Greedy takes a, b and c for $12; the optimum drops a and takes b, c and d for $15
Density order is a for 1.5, b for 1.33, c for 1.25, d for 1.2, so greedy packs a, b and c into 9kg and then cannot fit d in the remaining 3kg. The table finds that leaving the lightest item out frees exactly enough room for the heaviest, which is a trade no single-pass rule can see. Density greedy is provably optimal for FRACTIONAL knapsack and unboundedly bad here — that distinction, with a counterexample ready, is what the question is really asking.
See it run — The reconstruction lights rows d, c and b — and pointedly not a, the densest item.
What goes in a cell whose capacity is smaller than the row’s item weight?
Edge case reasoning
The value from directly above, unchanged — only the leave branch is legal there
The weight guard is what keeps the take branch from reading a negative column, and skipping it leaves the leave branch as the only option — a straight copy downward. On the trace this shows as a run of cells at the start of a row carrying the previous row’s numbers forward, until the capacity finally reaches the item’s weight and the first take appears. That transition is the clearest single picture of the recurrence.
See it run — The 5kg tent at capacity 4: one read from above, and the zero copies straight down.
The bag must be filled to EXACTLY W, not merely within it. What changes?
Edge case reasoning
Initialise every cell of row 0 to negative infinity except column 0, so infeasible capacities cannot look worth zero
In the at-most formulation an unreachable capacity is harmlessly zero, because zero is genuinely achievable by packing nothing. Under exact fill, zero is a lie — it lets the recurrence build on packings that do not exist. Seeding infeasible cells with negative infinity makes the impossibility propagate, and it is the standard adaptation for subset-sum and partition problems.
Why is fractional knapsack easy when the 0/1 version is NP-hard?
Comparison
Fractions let you always fill the bag exactly, so taking the densest first is provably optimal
With fractions there is never wasted capacity, so swapping any part of a solution for an equal weight of a denser item can only help — the exchange argument that makes greedy correct. The 0/1 constraint destroys that: taking the densest item can waste capacity no other item fits into, and repairing the waste may require reversing several earlier choices. One word of the problem statement moves it from n log n to NP-hard.
How do you turn this table into a solver for "can any subset sum to exactly T"?
Comparison
Use each item’s weight as its value and ask whether capacity T reaches T — or track booleans instead of values
Once value equals weight, the best achievable value within T is T exactly when some subset sums to T, so the corner answers the question directly. The boolean form is the same table with OR instead of max, which is cheaper and clearer. Partition-into-equal-halves is then subset-sum to half the total, so three interview problems collapse into one memorised loop.
Explain the knapsack table to someone who does not code. Say it out loud first.
Explain it plainly
You have a bag that holds ten kilos and a pile of things, each with a weight and a price, and you want the most valuable bagful. The obvious plan is to take the best value-for-weight first, then the next best, and so on. That plan is wrong, and it is wrong in a way you can feel: taking a light bargain first can leave you with a gap too small for the expensive thing you really wanted, and by then you have already committed. So instead of deciding in an order, you build a chart. Down the side you list the items one at a time; along the top you write every possible bag size from zero up to ten kilos. Each square asks one small question: if I were only allowed to consider the items down to this row, and my bag were only this big, what is the most I could carry? And each square has just two candidates — ignore this item, which is the square directly above, or take it, which means its price plus whatever the square above could manage with the leftover space. Write down the bigger of the two and move on. When you reach the bottom-right corner, that is your answer, and you can retrace your steps upward to see which items you actually took. Where the picture breaks down: it only works because the bag sizes are whole kilos you can list out. Make the bag hold a billion kilos and the chart has a billion columns, and the problem goes back to being genuinely hard — which it always was; the chart just happens to be a very good deal when the numbers are ordinary.
The listener should understand why obvious rules of thumb fail and what the grid is doing instead. A strong answer makes the greedy failure concrete and names the one thing the grid quietly assumes.