What you're seeing
You have items, each with a weight and a value, and a bag that holds only so much weight. Which subset maximizes value? Trying all 2ⁿ subsets is exponential. Dynamic programming builds a table instead: dp[i][w] is the best value achievable using only the first i items if the capacity were w. Each cell looks at just one new item and asks a single yes/no question — skip it (inherit the value from the row above) or take it (its value plus the best we could do with the remaining capacity, from the row above shifted left by its weight) — and keeps the larger. Fill the grid row by row; the bottom-right cell is the answer. Then we walk back up to see which items were chosen.
The rule
dp[0][w] = 0 # no items → no value
for i in 1..n:
for w in 0..W:
skip = dp[i-1][w]
take = (weightᵢ ≤ w) ? valueᵢ + dp[i-1][w - weightᵢ] : −∞
dp[i][w] = max(skip, take)
answer = dp[n][W] # backtrack to recover the items
The invariant
Each cell is exactly what it claims: dp[i][w] is the optimal value over all subsets of the first i items whose weight is ≤ w. The proof is induction with an exchange of cases. Consider the best subset for (i, w). Either it doesn't use item i — then it's a valid subset of the first i−1 items, so its value is dp[i−1][w] — or it does use item i, and removing that item leaves an optimal packing of the first i−1 items into capacity w − weightᵢ, worth dp[i−1][w − weightᵢ] (if it weren't optimal, we could swap in a better one and beat the supposed best — a contradiction). Those two cases are precisely skip and take, so taking their max is correct. This optimal substructure — an optimum built from optima of strictly smaller subproblems, each solved once — is the heart of every dynamic program.
The cost
The table has n·(W+1) cells and each costs O(1), so it's O(nW) — and since only the previous row is ever read, the space collapses to a single row, O(W). But notice W is a number, not the input size: writing W takes only log W bits, so O(nW) is exponential in the input length. That makes knapsack pseudo-polynomial, and the problem NP-hard — fast when capacities are small, but not a polynomial-time algorithm in general. For huge W there's instead an FPTAS that scales the values to get within (1−ε) of optimal in polynomial time.
In the wild
Knapsack is the model problem for "best subset under a budget," and the DP is a teaching cornerstone for optimal substructure. Its shape appears in cutting-stock and cargo loading, capital budgeting and portfolio selection under a spending cap, resource allocation and ad/bidding under quotas, and cryptography's history (the broken Merkle–Hellman knapsack cipher). The unbounded and bounded variants power coin-change and inventory problems, and the same row-by-row table idea generalizes to a whole family of subset-sum and partition problems.
Try this
Watch a single cell fill: it only ever reads two cells from the row above — that's the whole recurrence. Raise the Capacity and the table widens (the O(nW) cost made visible). At the end, follow the green backtrack: a cell that differs from the one directly above means "this item was taken," and we jump left by its weight — reading the chosen set straight off the table.
References
- Bellman, R. Dynamic Programming. Princeton University Press, 1957. The method.
- Cormen, Leiserson, Rivest & Stein. Introduction to Algorithms, 4th ed. (CLRS), §14 (Dynamic Programming) & §35.5 (FPTAS for subset-sum). MIT Press, 2022.
- Kellerer, Pferschy & Pisinger. Knapsack Problems. Springer, 2004 — the comprehensive reference.