What Is the 0/1 Knapsack Problem? The DP Pattern Explained

You're a thief with a bag that holds 5 kg. Three gems are on the table. You can't carry everything. Which ones do you take?

That's the knapsack problem. The setup sounds trivial. The naive solution checks every possible combination, and with 30 items that's over a billion subsets to evaluate while your interviewer watches the clock and quietly updates their debrief notes. The DP solution is one of the cleanest examples of how a well-chosen table turns an intractable search into a systematic fill.

If you understand 0/1 knapsack, you understand the DP pattern behind at least a dozen common interview problems.

The 0/1 Knapsack Problem: One Bag, One Decision Per Item

The 0/1 knapsack problem: given n items, each with weight w[i] and value v[i], and a bag with capacity W, find the maximum total value you can carry. Each item taken at most once. The "0/1" means all-or-nothing per item. No partial gems. You're a thief, not a barista.

Concrete example. Three gems, one bag:

Item	Weight	Value
Gem A	2 kg	$6
Gem B	2 kg	$10
Gem C	3 kg	$12

Bag capacity: 5 kg.

Enumerate the options: A+B (4 kg, $16), A+C (5 kg, $18), B+C (5 kg, $22), just C (3 kg, $12). The answer is B+C at $22. With three items that's fine. With 30 items there are over a billion subsets. You need a better approach.

Why Greedy Doesn't Save You

The natural instinct is to sort by value-to-weight ratio and grab the most efficient item first. Gem B has ratio 5, Gem C has 4, Gem A has 3. So take B (2 kg, $10), then C (3 kg, $12). Bag full at 5 kg, total $22. Worked this time.

It doesn't always. Suppose the bag holds 4 kg and you have items at $10/1kg, $6/3kg, $5/3kg. Best ratio is $10/1kg, take it. Now 3 kg remains. Take $6/3kg for total $16. But you could have skipped the first item and taken both the 3 kg items for $11.

Greedy is confident. Greedy does not look ahead. Greedy is the friend who orders first at a restaurant and accidentally takes the last thing you wanted.

Greedy has no way to account for how items combine. It can't look back. DP can, because it stores the best answer for every sub-capacity along the way.

For a deeper look at when greedy provably works versus when you need DP, see greedy vs dynamic programming.

Two Choices, Repeated n Times

The insight that makes DP possible: for each item, you face a binary decision. That's it. Two choices, n times. No branching factor that explodes, no need to track which combination you're on.

You're considering item i with weight w and value v. You have capacity c remaining. Two choices:

Skip it: best value from items 1..i-1 at capacity c.
Take it: v plus best value from items 1..i-1 at capacity c - w.

Written as a recurrence:

dp[i][c] = max(
    dp[i-1][c],               # skip item i
    v[i] + dp[i-1][c - w[i]] # take item i (only when w[i] <= c)
)

dp[i][c] = maximum value from the first i items with capacity c.

Base cases: dp[0][c] = 0 for all c (no items, no value) and dp[i][0] = 0 for all i (no capacity, no value). Every subproblem bottoms out here.

How the Table Fills

Row by row for our gem example. You're essentially a very organized accountant working for a jewel thief.

The full DP table for our gem example, row by row

Row 0: no items. Every cell is 0. Bleak, but correct.

Row 1: add Gem A (w=2, v=$6).

At capacity 0 or 1, Gem A doesn't fit. At capacity 2 and above, take it for $6.

cap: 0  1  2  3  4  5
      0  0  6  6  6  6

Row 2: add Gem B (w=2, v=$10).

At capacity 2: take B ($10) beats take A ($6). At capacity 4: take B ($10) with 2 kg left, where row 1 says $6 for A. So $16.

cap: 0  1  2   3   4   5
      0  0  10  10  16  16

Row 3: add Gem C (w=3, v=$12).

At capacity 3: take C ($12) beats the previous best ($10). At capacity 5: take C ($12) with 2 kg remaining, where row 2 says $10 for B. So $22.

cap: 0  1  2   3   4   5
      0  0  10  12  16  22

dp[3][5] = 22. That's the answer. Each cell took constant work. Here's the full implementation:

def knapsack(weights: list[int], values: list[int], capacity: int) -> int:
    n = len(weights)
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]

    for i in range(1, n + 1):
        w, v = weights[i - 1], values[i - 1]
        for c in range(capacity + 1):
            dp[i][c] = dp[i - 1][c]
            if c >= w:
                dp[i][c] = max(dp[i][c], dp[i - 1][c - w] + v)

    return dp[n][capacity]

Time complexity: O(n × W). You fill every cell of the (n+1) × (W+1) table, constant work per cell. Space complexity: O(n × W) for the table.

The Space Optimization (and the Easy Bug)

Row i only reads from row i-1. You don't need the full table. Use a 1D array and update it in place.

The catch: you must scan right to left. This is where most implementations go wrong, silently, with no error message to blame.

If you scan left to right, when you compute dp[c] using dp[c - w], that left-side value was already updated in the current pass. You'd be letting the same item be taken multiple times. You've accidentally written the "unlimited gem budget" problem instead of the "one gem per type" problem. The tests fail and you stare at code that looks completely correct.

Scanning right to left guarantees you're reading old values from the previous item's pass:

def knapsack_1d(weights: list[int], values: list[int], capacity: int) -> int:
    dp = [0] * (capacity + 1)

    for w, v in zip(weights, values):
        for c in range(capacity, w - 1, -1):  # right to left
            dp[c] = max(dp[c], dp[c - w] + v)

    return dp[capacity]

This cuts space to O(W). Left-to-right scan = unbounded knapsack (each item reusable). Right-to-left = 0/1 knapsack. One direction flip, two completely different problems, and no compiler warning to save you. Know this cold before you sit down.

For the theory behind why top-down memoization and this bottom-up tabulation produce identical results, see memoization vs tabulation.

The Same Pattern in Different Clothes

The 0/1 knapsack structure shows up constantly in disguise. Recognizing the shape matters more than memorizing the problem name.

Unbounded Knapsack (Coin Change): each item can be reused. Flip to left-to-right scan. The dynamic programming framework covers how to spot which variant you're facing.

Subset Sum (LeetCode 416, Partition Equal Subset Sum): a boolean variant. You want to know if some subset hits exactly a target weight. Same recurrence, True/False instead of max values.

def can_partition(nums: list[int]) -> bool:
    total = sum(nums)
    if total % 2 != 0:
        return False
    target = total // 2
    dp = [False] * (target + 1)
    dp[0] = True

    for num in nums:
        for c in range(target, num - 1, -1):
            dp[c] = dp[c] or dp[c - num]

    return dp[target]

Target Sum (LeetCode 494): assign + or - to each number, count combinations hitting a target. Reducible to subset sum with a sign transformation. Ones and Zeros (LeetCode 474): two constraints instead of one (count of 0s and count of 1s), but still the same item-in-or-out structure, just with a 2D capacity.

The unifying signal: "select a subset to maximize a value or hit a target, subject to a constraint." When you see that phrasing, start with knapsack. You'll be right more often than not.

What the Interview Is Actually Testing

The 0/1 knapsack problem itself rarely appears as an explicit question. Its pattern is everywhere.

Coin Change (minimize coins to reach an amount), Coin Change II (count combinations), Partition Equal Subset Sum, Target Sum, Last Stone Weight II all reduce to the same table-fill structure. Most candidates get the recurrence right. Then the loop runs left to right, the test case fails, they stare at code that looks correct for 90 seconds, and eventually change a variable name to see if that helps. It does not help.

The interview tests whether you recognize the "items and capacity" frame, write the recurrence correctly, and remember the scan direction. The scan direction is the one-line detail that separates a pass from a fail on three different LeetCode problems.

Practicing this kind of problem out loud, where you explain state definition, recurrence, and scan direction to a live interviewer, is a different skill than solving it silently. SpaceComplexity runs timed mock interviews on exactly these problems with rubric-based feedback on whether your explanation is as tight as your code. Try one before your next interview.

For a broader map of which problems call for DP versus other approaches, how to recognize dynamic programming problems lays out the signals.

Quick Reference

0/1 knapsack: maximize value from n items within weight W, each item taken at most once.
Brute force is O(2^n). DP is O(n × W) time, reducible to O(W) space.
Recurrence: dp[i][c] = max(skip, take) where take subtracts the item's weight from remaining capacity.
Compress to 1D by scanning right to left per item. Left to right gives unbounded knapsack.
Core interview variants: Partition Equal Subset Sum (416), Coin Change (322), Coin Change II (518), Target Sum (494), Ones and Zeros (474).
The scan direction detail is the most common implementation mistake. Know why it matters, not just which way.