In 0/1 knapsack, what does dp[i][w] hold and which two candidates does the recurrence compare?
answer
- each item gets one yes-or-no decision
- two candidates per cell, not one
- what budget is left after taking it
- the leftover budget is solved by earlier items
- compare the previous row at two columns
basics
~20 sdp[i][w] is the best total value reachable using only the first i items within a capacity of w. The recurrence takes the larger of leaving item i out, dp[i-1][w], and taking it, value[i] + dp[i-1][w - weight[i]], when it fits.
solid answer
~50 sPicture a survey drone with a lift limit, and instruments that each have a weight and a science value; every instrument either flies or stays behind. Define `dp[i][w]` as the best value obtainable from the first `i` instruments when the limit is `w` — at most `w`, not exactly `w`. The base row `dp[0][w] = 0` says nothing loaded, nothing gained. For each instrument you compare two candidates: leave it, giving `dp[i-1][w]`; or take it, paying its weight and collecting its value, giving `value[i] + dp[i-1][w - weight[i]]`, which is only legal when `weight[i] <= w`. The maximum of the two is the cell. The take branch reads row `i-1` on purpose — that is the single index that stops the same instrument being loaded twice. The answer sits at `dp[n][W]`, filled in O(nW) time.
go deeper
Be ready to say in one sentence what a knapsack cell means, and to name the two candidates it compares: skip the item, or take it and pay its weight out of the budget.
Explain why the take branch reads the previous row — that single index is what limits each item to one copy — and derive the base row rather than reciting it.
Defend the at-most-capacity state choice, show the answer can be read straight off the final cell, and reconstruct the chosen load by walking the finished table backwards.
Own the prior question: is a capacity-indexed table the right shape for this workload at all, given how large the limit and the item count actually get on real traffic?
## The setting A survey drone can lift a fixed number of kilograms. Each candidate instrument is a record carrying a weight and a science value, and each exists in exactly one copy: it flies, or it stays on the bench. Maximising total science value under the lift limit is the 0/1 knapsack problem — the "0/1" naming the only two multiplicities allowed per item. ## The state, read carefully `dp[i][w]` = the maximum total value achievable using only the **first i** instruments, when the capacity available is `w`. Two details in that sentence carry the whole method. *"Only the first i"* means the state ranges over a **prefix** of the item list. Items enter the problem one at a time, and each is decided exactly once. That is what makes the choose-or-skip decision tree collapse into a table: two different subsets of the first `i` items that consume the same capacity are interchangeable from here on, so only the better one needs remembering. *"Capacity w"* means **at most** `w`, not exactly `w`. A cell is allowed to describe a load lighter than its column. This makes every row non-decreasing from left to right, and it is why the final answer is read directly at `dp[n][W]` instead of being searched for across the last row — the best 7 kg load is already reported in the 9 kg column. ## Base cases `dp[0][w] = 0` for every `w`: with no instruments offered, nothing can be loaded whatever the limit. With positive weights, `dp[i][0] = 0` likewise. ## The recurrence For instrument `i` with `weight[i]` and `value[i]`: - If `weight[i] > w`: `dp[i][w] = dp[i-1][w]`. It does not fit; the only option is to leave it. - Otherwise: `dp[i][w] = max(dp[i-1][w], value[i] + dp[i-1][w - weight[i]])`. The **leave** branch inherits the best answer that the earlier instruments could manage with the same budget. The **take** branch spends `weight[i]` of the budget, banks `value[i]`, and hands the remaining `w - weight[i]` back to the earlier instruments to solve. The index that matters is the row on the take branch: `i-1`, never `i`. Row `i-1` means "instrument `i` has not been offered yet", so the residual budget cannot possibly be filled with another copy of the same instrument. Writing `dp[i][w - weight[i]]` there would silently allow repeats and answer a different question. ## Filling order and cost Fill rows in increasing `i`, each row across `w = 0..W`. Every cell is O(1) work, so the table costs O(nW) time and O(nW) space in this two-dimensional form. Note that the second factor is the **capacity limit**, not the number of items — that distinction matters when you decide whether the table is affordable at all. ## Reading and reconstructing the answer The optimum is `dp[n][W]`. To recover *which* instruments were loaded, walk backwards from `(n, W)`: if `dp[i][w] == dp[i-1][w]`, instrument `i` was not needed — move to `(i-1, w)`. Otherwise it was taken — record it and move to `(i-1, w - weight[i])`. That is O(n) extra steps and no extra table. On a tie, treating the item as skipped is safe: some optimal load omits it. ## What people get wrong - **Misreading the state.** `dp[i][w]` is not "the value of item `i` at weight `w`"; it is a whole sub-answer over a prefix of items. - **Confusing at-most with exactly.** A table whose cells mean *exactly* `w` needs a different initialisation (only column 0 reachable) and the answer becomes a maximum over reachable columns. Both formulations work; mixing them produces a table that reports zero for perfectly good loads. - **Dropping the fit guard.** Without `weight[i] <= w`, the take branch indexes a negative column. - **Assuming structure that is not required.** Weights need not be distinct, sorted, or coprime; only non-negative and integral, because they index a table. ## The boolean cousin When an item's weight and its value are the same number, or when the question is merely "can this budget be met", the `max` collapses into a reachability OR and the value table becomes a table of true/false cells. Same skeleton, cheaper cells.
- How do you recover which instruments were actually loaded, not just the total value?Walk backwards from the last cell. At `(i, w)`, if `dp[i][w] == dp[i-1][w]` the item was skipped, so move to `(i-1, w)`; otherwise it was taken, so record it and move to `(i-1, w - weight[i])`. That is O(n) steps on the finished table with no extra storage, and on a tie treating the item as skipped is safe because some optimal load omits it.
- Why does the table carry every capacity from 0 to the limit rather than just the limit itself?Because the take branch asks about a smaller residual budget. Once you spend an item's weight, the remaining problem is the same problem at a lower capacity, and that sub-answer has to exist somewhere. Every column is a genuine subproblem that some branch reaches; dropping the intermediate columns would leave the recurrence with nothing to read.
- What happens if one instrument weighs zero but carries positive value?It is taken in every column. The recurrence still works unchanged: the take branch evaluates `value[i] + dp[i-1][w]`, which beats the leave branch `dp[i-1][w]` whenever the value is positive, and the fit guard is trivially satisfied. Nothing breaks, because the take branch still reads the previous row and so still uses the item at most once.
Each instrument is a single yes/no switch, and the table remembers the best packing for every remaining lift budget, so a later decision never forces you to re-open an earlier one.
saying these in an interview costs you the question
- Says dp[i][w] is the value of item i at weight w
- Indexes the take branch at the current row, allowing reuse
- Cannot state a base case for the empty prefix
- Forgets the guard for an item that does not fit
- Thinks the answer must be hunted for across the last row