The Knapsack Problem

The knapsack problem asks: given a set of items, each with a weight and a value, and a bag that can carry at most a fixed total weight, which items should you pack to maximize total value? It shows up constantly in practice — choosing which files fit on a disk, which ads fit in a budget, which orders fit on a delivery truck — and it is one of the most common interview questions used to test whether you can recognize and apply dynamic programming. This lesson covers the classic 0/1 knapsack variant, where each item can be taken at most once (you either put it in the bag or you don’t), and shows why a greedy ‘grab the best ratio first’ approach fails here even though it works for a closely related problem.

Overview / How It Works

Imagine packing for a day hike with a backpack that can hold at most 4 kilograms. You are choosing among a water bottle (3 kg, value 10), a map (1 kg, value 6), a compass (1 kg, value 4), and snacks (2 kg, value 5). You cannot split the water bottle in half — you either bring it or you don’t. This all-or-nothing constraint is what makes it the 0/1 knapsack: for every item, the amount taken is 0 or 1, never a fraction.

0/1 vs. Fractional Knapsack

If items were divisible — think gold dust instead of gold bars — you could sort by value-to-weight ratio and greedily fill the bag with the best ratio first, taking a partial amount of the last item that doesn’t fully fit. That greedy strategy is provably optimal for the fractional knapsack problem. But once items are indivisible, greedy can fail: the single best-ratio item might not combine well with anything else, while two slightly-worse-ratio items might fit together perfectly and beat it. Because greedy commits to a choice without looking ahead, it never explores the ‘what if I skip this one’ branch — and the 0/1 knapsack genuinely needs to consider both possibilities for every item.

The Recurrence

The key insight is that the whole problem contains smaller, identical copies of itself. Suppose you already know the best value achievable using only the first i - 1 items, for every possible remaining capacity. Then the best value using all i items is easy: look at item i and decide. If it doesn’t fit in the remaining capacity, you must skip it. If it does fit, you take the better of two choices — skip it (same answer as before), or take it (its value, plus the best answer for the first i - 1 items with the capacity reduced by its weight). Written as a recurrence, with dp[i] meaning ‘the best value using only the first i items with capacity c‘:

dp[i] = dp[i - 1] when weights[i-1] > c, otherwise dp[i] = max(dp[i - 1], dp[i - 1]] + values[i-1]).

The same (i, c) subproblem gets reached again and again from different branches of the naive recursive solution — this is the overlapping subproblems property. Combined with optimal substructure (the optimal answer is built from optimal answers to smaller subproblems), caching each (i, c) result — either top-down with memoization or bottom-up with a table — turns an exponential brute force into a polynomial-time algorithm.

Time and Space Complexity

Let n be the number of items and capacity be the knapsack’s weight limit. The table below compares the main approaches.

Approach	Time	Space	Why
Brute force (every subset)	O(2^n)	O(n)	Each of the n items is independently included or excluded, so there are 2^n subsets to check; space is just the recursion depth.
Top-down recursion + memoization	O(n · capacity)	O(n · capacity)	There are only n · capacity distinct (i, remaining capacity) states; memoization computes each exactly once.
Bottom-up tabulation (2D array)	O(n · capacity)	O(n · capacity)	Fills an (n+1) × (capacity+1) table, doing one O(1) computation per cell.
Bottom-up, space-optimized (1D array)	O(n · capacity)	O(capacity)	Each row only ever needs the previous row, so a single reused array (updated right-to-left) suffices.

Notice the running time depends on the numeric value of capacity, not just on n. This is called pseudo-polynomial time: the algorithm is polynomial in the magnitude of the input numbers, not in the number of bits needed to represent them. A capacity of 10 is trivial; a capacity of one billion makes a table with a billion columns impractical even if n is tiny. That distinction is worth remembering — it’s a common interview follow-up (‘what if the capacity were huge?’).

The top-down recursive version has a call stack depth of at most n (one frame per item considered), which is far below Python’s default recursion limit of about 1000 for any reasonable item count. Still, the bottom-up table avoids recursion entirely, which is one more reason it’s usually preferred in production code.

Examples

Example 1: Basic 0/1 Knapsack with a Full DP Table

This builds the complete 2D table described above and reads the answer out of its final cell.

def knapsack_2d(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):
        weight = weights[i - 1]
        value = values[i - 1]
        for c in range(capacity + 1):
            if weight <= c:
                dp[i] = max(dp[i - 1], dp[i - 1] + value)
            else:
                dp[i] = dp[i - 1]
    return dp[n][capacity]


if __name__ == "__main__":
    weights = [1, 3, 4, 5]
    values = [1, 4, 5, 7]
    capacity = 7
    print(f"Maximum value: {knapsack_2d(weights, values, capacity)}")

Output:

Maximum value: 9

Tracing it: with items (weight, value) pairs (1,1), (3,4), (4,5), (5,7) and capacity 7, the best combination turns out to be the second and third items — weights 3 and 4 sum to exactly 7, and their values 4 and 5 sum to 9. No other combination that fits in 7 kg beats that, which is exactly what the table computes in dp[4][7].

Example 2: Recovering Which Items Were Chosen

Knowing the best value is often not enough — you usually also want to know which items to actually pack. Walking backward through the table lets you reconstruct the choice at each step: if dp[i] differs from dp[i - 1], item i must have been taken.

def knapsack_with_items(
    weights: list[int], values: list[int], names: list[str], capacity: int
) -> tuple[int, list[str]]:
    n = len(weights)
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        weight = weights[i - 1]
        value = values[i - 1]
        for c in range(capacity + 1):
            if weight <= c:
                dp[i] = max(dp[i - 1], dp[i - 1] + value)
            else:
                dp[i] = dp[i - 1]

    selected: list[str] = []
    c = capacity
    for i in range(n, 0, -1):
        if dp[i] != dp[i - 1]:
            selected.append(names[i - 1])
            c -= weights[i - 1]
    selected.reverse()
    return dp[n][capacity], selected


if __name__ == "__main__":
    names = ["Water", "Map", "Compass", "Snacks"]
    weights = [3, 1, 1, 2]
    values = [10, 6, 4, 5]
    capacity = 4
    best_value, chosen_items = knapsack_with_items(weights, values, names, capacity)
    print(f"Best value: {best_value}")
    print(f"Items chosen: {chosen_items}")

Output:

Best value: 16
Items chosen: ['Water', 'Map']

With a 4 kg capacity, packing the Water bottle (3 kg, value 10) and the Map (1 kg, value 6) uses exactly 4 kg for a value of 16. Every other combination that fits — Compass+Snacks+Map (4 kg, value 15), Water+Compass (4 kg, value 14), and so on — scores lower, so the backward walk correctly lands on Water and Map.

Example 3: Reducing Space to O(capacity)

If you only need the maximum value (not the item list), you don’t need the full 2D table — each row only depends on the row above it, so one 1D array can be reused, provided you update it from right to left.

def knapsack_optimized(weights: list[int], values: list[int], capacity: int) -> int:
    dp = [0] * (capacity + 1)
    for weight, value in zip(weights, values):
        for c in range(capacity, weight - 1, -1):
            dp = max(dp, dp + value)
    return dp[capacity]


if __name__ == "__main__":
    weights = [1, 3, 4, 5]
    values = [1, 4, 5, 7]
    capacity = 7
    print(f"Maximum value: {knapsack_optimized(weights, values, capacity)}")

Output:

Maximum value: 9

Same items, same capacity, same answer (9) as Example 1 — but the array is only capacity + 1 entries long instead of (n + 1) × (capacity + 1). The right-to-left iteration is essential here; the Common Mistakes section below shows exactly what breaks if you iterate left to right instead.

How It Works Step by Step

Let’s trace the table by hand for a tiny instance: items with (weight, value) pairs (2, 3), (3, 4), (4, 5), and capacity 5. Each row below shows the best value achievable for each capacity after considering one more item.

After considering	c=0	c=1	c=2	c=3	c=4	c=5
No items	0	0	0	0	0	0
+ item (w=2, v=3)	0	0	3	3	3	3
+ item (w=3, v=4)	0	0	3	4	4	7
+ item (w=4, v=5)	0	0	3	4	5	7

Look at c=5 after the second item: skipping it keeps the previous row’s value at c=5, which is 3; taking it adds its value 4 to whatever the first row achieved at the remaining capacity 5 - 3 = 2, which is 3, for a total of 7. Since max(3, 7) = 7, the cell becomes 7. Now look at c=4 after the third item: skipping keeps 4 (the row above); taking it adds value 5 to the remaining capacity 4 - 4 = 0, which is worth 0, for a total of 5. Since max(4, 5) = 5, that cell updates to 5. The final answer, in the bottom-right cell, is 7 — achieved by packing the first two items (weights 2 and 3, total weight 5, total value 7).

Common Mistakes

Mistake 1: Iterating the 1D array left to right

The space-optimized version only works if you scan capacities from high to low. Scanning low to high lets an item’s own just-updated value feed into a later cell in the same pass, which is equivalent to allowing that item to be used more than once — that’s the unbounded knapsack, not the 0/1 knapsack.

def knapsack_wrong(weights: list[int], values: list[int], capacity: int) -> int:
    dp = [0] * (capacity + 1)
    for weight, value in zip(weights, values):
        for c in range(weight, capacity + 1):  # BUG: forward order reuses items
            dp = max(dp, dp + value)
    return dp[capacity]


if __name__ == "__main__":
    weights = [2, 3, 4]
    values = [3, 4, 5]
    capacity = 4
    print(f"Wrong result: {knapsack_wrong(weights, values, capacity)}")

Output (buggy):

Wrong result: 6

With only one item of weight 2 and value 3 available, there is no legal way to reach a value of 6 within 4 kg using distinct items — the true best is 5 (the single weight-4 item). The buggy version reaches 6 by silently ‘reusing’ the weight-2 item twice. The fix is to iterate capacities from high to low, so each cell only ever reads values that reflect the previous item’s state:

def knapsack_correct(weights: list[int], values: list[int], capacity: int) -> int:
    dp = [0] * (capacity + 1)
    for weight, value in zip(weights, values):
        for c in range(capacity, weight - 1, -1):  # backward order: each item used once
            dp = max(dp, dp + value)
    return dp[capacity]


if __name__ == "__main__":
    weights = [2, 3, 4]
    values = [3, 4, 5]
    capacity = 4
    print(f"Correct result: {knapsack_correct(weights, values, capacity)}")

Output:

Correct result: 5

Mistake 2: A mutable default argument in the memo dictionary

A tempting way to write the top-down version is to default the memo dictionary in the function signature. That default is created exactly once, when the function is defined, and is then silently shared across every call that doesn’t pass its own dictionary — including calls with completely different weights and values lists. Since the cache key is only (i, capacity), a later call can get back a stale answer computed for different items.

def knapsack_topdown_buggy(
    i: int, capacity: int, weights: list[int], values: list[int], memo: dict = {}
) -> int:
    if i == 0 or capacity == 0:
        return 0
    if (i, capacity) in memo:
        return memo[(i, capacity)]
    if weights[i - 1] > capacity:
        result = knapsack_topdown_buggy(i - 1, capacity, weights, values, memo)
    else:
        skip = knapsack_topdown_buggy(i - 1, capacity, weights, values, memo)
        take = values[i - 1] + knapsack_topdown_buggy(
            i - 1, capacity - weights[i - 1], weights, values, memo
        )
        result = max(skip, take)
    memo[(i, capacity)] = result
    return result


if __name__ == "__main__":
    print(knapsack_topdown_buggy(2, 5, [1, 3], [10, 10]))
    print(knapsack_topdown_buggy(2, 5, [100, 100], [1, 1]))

Output (buggy):

20
20

The second call uses items of weight 100, which cannot possibly fit in a capacity of 5 — the correct answer is 0. Instead it prints 20, the leftover answer cached from the first, unrelated call, because (i, capacity) = (2, 5) was already a key in the shared dictionary. The fix is to default to None and create a fresh dictionary inside the function body:

def knapsack_topdown(
    i: int, capacity: int, weights: list[int], values: list[int], memo: dict | None = None
) -> int:
    if memo is None:
        memo = {}
    if i == 0 or capacity == 0:
        return 0
    if (i, capacity) in memo:
        return memo[(i, capacity)]
    if weights[i - 1] > capacity:
        result = knapsack_topdown(i - 1, capacity, weights, values, memo)
    else:
        skip = knapsack_topdown(i - 1, capacity, weights, values, memo)
        take = values[i - 1] + knapsack_topdown(
            i - 1, capacity - weights[i - 1], weights, values, memo
        )
        result = max(skip, take)
    memo[(i, capacity)] = result
    return result


if __name__ == "__main__":
    print(knapsack_topdown(2, 5, [1, 3], [10, 10]))
    print(knapsack_topdown(2, 5, [100, 100], [1, 1]))

Output:

20
0

Now each call starts with its own empty memo, so the second call correctly reports 0.

Best Practices

• Reach for 0/1 knapsack DP whenever you see ‘choose a subset of items, each usable at most once, to maximize/minimize something under a capacity constraint’ — that phrasing is the giveaway.
• Use the space-optimized 1D array when you only need the best value; keep the full 2D table (or store explicit choice flags) if you need to reconstruct which items were chosen, since backtracking needs the earlier rows.
• In the 1D version, always iterate capacity from high to low for 0/1 knapsack; iterate low to high only if you deliberately want the unbounded knapsack (unlimited copies of each item).
• Reach for greedy by value-to-weight ratio only when items are truly divisible (fractional knapsack); don’t assume it works once items become indivisible.
• Recognize related problems as knapsack in disguise: subset sum (value equals weight, ask whether some subset hits a target exactly) and ‘partition into two equal-sum subsets’ both reuse the same recurrence.
• Remember the pseudo-polynomial warning: if the capacity can be astronomically large relative to n, the DP table itself becomes the bottleneck, and you’ll need a different technique (e.g., branch and bound, or approximation) rather than a bigger table.
• Prefer the bottom-up table for interview settings unless the recursive formulation is genuinely easier to state first — then convert to iterative once the recurrence is clear.

Practice Exercises

1. Given weights = [5, 4, 6, 3] and values = [10, 40, 30, 50] with capacity 10, write knapsack_optimized-style code to find the maximum value. Check your work: the expected maximum value is 90.
2. Subset sum: given nums = [3, 34, 4, 12, 5, 2] and a target of 9, determine whether any subset of nums sums to exactly 9. Hint: this is knapsack where ‘value’ and ‘weight’ are both the number itself, and you ask whether dp[n][target] == target. Expected result: True (using 4 and 5).
3. Partition equal subset sum (a common interview question): given nums = [1, 5, 11, 5], determine whether it can be split into two subsets with equal sums. Hint: compute the total sum; if it’s odd, the answer is immediately False, otherwise run subset-sum for target total // 2. Expected result: True (one subset is {11}, the other is {1, 5, 5}, each summing to 11).

Summary

• The 0/1 knapsack problem picks a subset of items, each usable 0 or 1 times, to maximize total value without exceeding a weight capacity.
• It has optimal substructure and overlapping subproblems, which is exactly what makes dynamic programming applicable; the recurrence is dp[i] = max(dp[i-1], dp[i-1][c-weight]+value) when the item fits, else dp[i] = dp[i-1].
• Time complexity is O(n · capacity) for both the top-down memoized and bottom-up tabulated approaches, versus O(2^n) for brute force; this is pseudo-polynomial, since it depends on the numeric size of capacity, not just the item count.
• Space can be reduced from O(n · capacity) to O(capacity) with a 1D array, but only if you iterate capacities from high to low — iterating low to high accidentally reuses items.
• Greedy by value-to-weight ratio is optimal for the fractional knapsack (divisible items) but is not correct for the 0/1 knapsack (indivisible items).
• Reconstructing which items were chosen requires walking backward through the full table, comparing dp[i] to dp[i-1].
• Watch out for mutable default arguments (e.g. memo: dict = {}) in recursive memoized solutions — use None and initialize inside the function instead.
• Subset sum and equal-subset-sum partitioning are the same recurrence in disguise, and are common interview follow-ups once you know knapsack.