Knapsack Problem Explained from First Principles

You've probably memorized the knapsack recurrence. You can write dp[i][w] = max(dp[i-1][w], dp[i-1][w-weight[i]] + value[i]) from memory. But ask yourself why that recurrence is correct, why those are the only two terms, why i-1 and not i, and the explanation falls apart. You won't find the knapsack problem explained from the decision that produces the recurrence in most resources. Instead, most resources teach it as a formula to apply.

The knapsack problem explained in plain terms

The 0/1 knapsack problem asks you to select items with given weights and values to maximize total value without exceeding a weight capacity. Each item can be included once or not at all. Every item presents one binary decision: you take it or you leave it.

That binary constraint makes brute force exponential. With n items, you've got 2^n possible subsets. For 20 items, that's over a million combinations, and for 40 it's over a trillion. No amount of pruning makes exhaustive search practical at scale.

But knapsack has optimal substructure. The best solution for n items at capacity w depends only on the best solutions for n-1 items at specific smaller capacities. That's the dependency that dynamic programming exploits.

The knapsack problem's recurrence explained

Start with the last item, item n. You have exactly two choices:

If you don't include item n, the best value you can get is whatever you could get from items 1 through n-1 with the full capacity still available. If you include item n, you gain value[n], but you've consumed weight[n] of your capacity. The best value for the remaining items (1 through n-1) is now constrained to capacity w - weight[n].

The optimal answer is whichever choice gives more value. That's the entire recurrence:

`
dp[i][w] = max(dp[i-1][w], dp[i-1][w - weight[i]] + value[i])
`

There's also a guard condition. If weight[i] > w, item i can't fit, so the only option is to exclude it and dp[i][w] = dp[i-1][w].

Why i-1 and not i? Because this is 0/1 knapsack. Each item is used at most once. When you're deciding about item i, the remaining subproblem only involves items before i. If the recurrence used dp[i][w - weight[i]], you'd be allowing item i to be included multiple times. That's a different problem entirely (unbounded knapsack).

The base cases follow from the definition. With zero items, the best value at any capacity is 0, so dp[0][w] = 0 for all w. With zero capacity, you can't include anything, so dp[i][0] = 0 for all i.

Building the knapsack table frame by frame

Recurrences make more sense when you trace them on real numbers. Take these 4 items.

`
| Item | Weight | Value | |------|--------|-------| | A | 2 | 3 | | B | 3 | 4 | | C | 4 | 5 | | D | 5 | 8 |
`

Capacity = 5. Build a table where rows are items (plus a row 0 for the empty set) and columns are capacities 0 through 5.

You can trace through a few cells to see the decision playing out.

At dp[1][2] (item A, capacity 2), A weighs 2 and fits. Excluding gives dp[0][2] = 0, while including gives dp[0][0] + 3 = 3. The max is 3, so you take A. Moving to dp[2][5] (items A-B, capacity 5), B weighs 3 and also fits. Excluding gives dp[1][5] = 3 (just A), while including gives dp[1][2] + 4 = 3 + 4 = 7. The max is 7, so you take both A and B.

At dp[3][5] (items A-C, capacity 5), C weighs 4 and fits, but excluding gives dp[2][5] = 7 (A+B), while including gives dp[2][1] + 5 = 0 + 5 = 5. The exclude path wins, so you don't take C.

At dp[4][5] (items A-D, capacity 5), D weighs 5 and fits. Excluding gives dp[3][5] = 7 (A+B), while including gives dp[3][0] + 8 = 0 + 8 = 8. The include path wins, so you take D alone.

The answer is 8, taking only item D. Items A and B together weigh 5 and give value 7, but item D alone weighs 5 and gives value 8. Having more items doesn't guarantee more value, because both branches get compared at every cell and the recurrence picks the winner.

From 2D to 1D: the space optimization

The recurrence only looks at row i-1 to fill row i. That means you don't need all n rows in memory at once. A single 1D array of size W+1 is enough, as described in the classic optimization of this problem.

There's a catch, though. If you fill the array left to right (increasing w), you'll overwrite values that later cells in the same row still need. When you compute dp[w], the value dp[w - weight[i]] might already reflect the current item, not the previous row. That accidentally creates the unbounded knapsack behavior, allowing items to be reused.

The fix: iterate capacity in reverse (from W down to weight[i]). That way, when you read dp[w - weight[i]], it still holds the value from the previous item's pass.

You get the same answer with O(W) space instead of O(n * W). The reverse iteration isn't a trick. It's what the 0/1 constraint requires, because each item can be used at most once. If you see a knapsack variant where items can be reused, iterate forward instead. The direction of the inner loop tells you the reuse policy.

The knapsack problem family

Once the include or exclude decision is clear, you'll start recognizing it in problems that don't mention "knapsack" at all.

Subset Sum: Asks whether a set of integers contains a subset that sums to exactly a target. This is knapsack where weight equals value and you're checking if dp[n][target] == target. The decision stays the same, include this number or skip it.

Equal Partition: Asks whether you can split an array into two subsets with equal sum. You first check if total sum is even. If it is, this reduces to Subset Sum with target = total/2, using the same binary decision and the same table shape. Minimum Partitioning is a close relative that splits an array into two subsets to minimize the difference between their sums. You find the largest achievable sum that doesn't exceed total/2 (a Subset Sum variant), then the answer is total - 2 * that sum.

All of these share the same core decision, at each element, include it or skip it. The table dimensions and the value function change, but the recurrence shape stays the same. That's why understanding why the recurrence works matters more than memorizing it. If you can reason about the decision, you can rebuild the recurrence for any variant without looking it up.

Recognizing knapsack in the wild

Knapsack is one of several DP pattern families. Recognizing when a new problem is a knapsack variant means training your identification layer, where you learn to read a problem statement and spot the triggers that point to this pattern. If a problem has binary include/exclude decisions over items with a resource constraint, you already know the recurrence shape.

For the full progression across DP pattern families (Coin Change, LCS, LIS, Edit Distance, Grid DP, and knapsack), see our complete guide to dynamic programming. If you're still working on how to identify which problems need DP at all, start there.

Codeintuition's Dynamic Programming course covers knapsack with this same derivation first approach. You build the recurrence before seeing the solution, trace the table before writing code, then apply it to variants with increasing difficulty. The free Arrays course uses the same teaching model, so you can test whether it fits your learning style before committing to the full platform at $79.99/year.

Six months ago, you stared at a knapsack problem and thought "I know there's a 2D table involved." You wrote the recurrence from memory, got the indices wrong, spent 20 minutes debugging. Now you derive it from the decision. At each item you include it or exclude it, and the only state you need is the item index and remaining capacity. The recurrence follows directly from those two questions, and understanding why the formula exists is what actually got you there.