vault

01 Knapsack

17 min read

01 Knapsack

The 0/1 Knapsack Problem asks: given n items, each with a positive integer weight w_i and value v_i, and a knapsack with integer capacity W, choose a subset of items to put in the knapsack so that the total weight is at most W and the total value is maximized — with the constraint that every item is either taken (1) or skipped (0). It is the canonical 2D dynamic-programming problem and the gateway to a whole family of “pick a subset under a budget” interview questions, including subset-sum, partition, and target-sum. The standard solution is O(nW) time and O(nW) space, reducible to O(W) space with the rolling-array trick — but the 1D version has a famously vicious iteration-order pitfall.

1. Intuition — The Hiker’s Backpack

Imagine you are packing a backpack for a hike. Your backpack can carry at most W = 10 kilograms. On the table in front of you are several items: a tent (5 kg, value 60), a sleeping bag (3 kg, value 50), a stove (2 kg, value 40), a book (1 kg, value 10), and a camera (4 kg, value 50). Your goal is to maximize the total value of what you bring without exceeding the weight limit. Each item is a single physical object — you either pack it whole or leave it; you cannot pack half a tent. That “all-or-nothing” constraint is the 0/1 in 0/1 Knapsack and is what distinguishes it from the fractional knapsack problem (which allows partial items and is solvable greedily by value-density v_i / w_i).

The combinatorial reality: with n items, there are 2^n subsets to consider. For n = 30 that’s about a billion — already too slow to brute-force inside an interview. DP exploits a key observation: once we have decided the fate of items 1..i and are left with capacity c, the best we can do from the remaining items 1..i depends only on (i, c) — not on the path that got us here. That is the optimal substructure that makes DP work, and it gives us a state space of size n × W instead of 2^n.

The 0/1 Knapsack problem was first formalized by George Dantzig in 1957 (“Discrete-variable extremum problems,” Operations Research); it is NP-hard in the general case (Karp’s 1972 list of 21 NP-complete problems includes Subset Sum, a special case). The DP solution we describe here is pseudo-polynomial — its running time O(nW) is polynomial in n and in the value of W, but exponential in the number of bits needed to write W. So if W = 10^18, the DP is useless even though n is small. This subtlety is the difference between “solvable for interview-sized inputs” and “polynomial in the formal complexity sense.”

2. Tiny Worked Example

Items (1-indexed):

iweight w_ivalue v_i
123
234
345
456

Capacity W = 5.

State: dp[i][w] = maximum value attainable using a subset of items 1..i with total weight at most w.

Recurrence: for each item i and capacity w,

dp[i][w] = max( dp[i-1][w],                              # skip item i
                dp[i-1][w - w_i] + v_i  if w_i ≤ w )     # take item i

Base cases: dp[0][w] = 0 for every w (no items → no value); dp[i][0] = 0 (no capacity → no value).

We fill the 2D table row by row (i = 1..4), each row from w = 0..5:

After i = 0 (empty row, all zeros):

w →012345
i=0000000

After i = 1 (item 1: weight 2, value 3). For w < 2, can’t take it. For w ≥ 2, max(skip=0, take = 0+3 = 3):

w →012345
i=1003333

After i = 2 (item 2: weight 3, value 4). For w < 3 we can only skip → carry down from row 1. For w = 3: max(skip=3, take=dp[1][0]+4=4) = 4. For w = 4: max(skip=3, take=dp[1][1]+4=4) = 4. For w = 5: max(skip=3, take=dp[1][2]+4=3+4=7) = 7:

w →012345
i=2003447

After i = 3 (item 3: weight 4, value 5). For w < 4, carry down. For w = 4: max(skip=4, take=dp[2][0]+5=5) = 5. For w = 5: max(skip=7, take=dp[2][1]+5=0+5=5) = 7:

w →012345
i=3003457

After i = 4 (item 4: weight 5, value 6). For w < 5, carry down. For w = 5: max(skip=7, take=dp[3][0]+6=6) = 7:

w →012345
i=4003457

Final answer: dp[4][5] = 7, achieved by items {1, 2} (weights 2+3=5, values 3+4=7).

Notice that adding item 3 (weight 4, value 5) didn’t improve anything at capacity 5 because to fit it we would have to drop something — and there’s no improvement to be had. Item 4 (weight 5, value 6) standing alone gives only 6 < 7. The DP found the right combination by considering both alternatives at every cell.

3. Pseudocode

knapsack_01(weights, values, W):
    n := length(weights)
    dp := 2D array of size (n+1) × (W+1), all zeros
    for i := 1 to n:
        for w := 0 to W:
            # option 1: skip item i
            dp[i][w] := dp[i-1][w]
            # option 2: take item i (if it fits)
            if weights[i-1] ≤ w:
                take := dp[i-1][w - weights[i-1]] + values[i-1]
                if take > dp[i][w]:
                    dp[i][w] := take
    return dp[n][W]

The iteration order is “outer over items, inner over capacities.” Because each cell dp[i][*] only depends on the previous row dp[i-1][*], we can collapse to 1D — but only if we iterate the inner loop in the right direction (see §6).

4. Python Implementation

4.1 Bottom-Up Tabulation, 2D

def knapsack_2d(weights: list[int], values: list[int], W: int) -> int:
    n = len(weights)
    dp = [[0] * (W + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        wi, vi = weights[i - 1], values[i - 1]
        for w in range(W + 1):
            dp[i][w] = dp[i - 1][w]                         # skip
            if wi <= w:
                take = dp[i - 1][w - wi] + vi
                if take > dp[i][w]:
                    dp[i][w] = take
    return dp[n][W]

Straightforward and easy to debug because every intermediate cell is preserved. Use this version when you also need to reconstruct the chosen items (you trace back through the table; see §7).

4.2 Bottom-Up Tabulation, 1D Rolling Array

def knapsack_1d(weights: list[int], values: list[int], W: int) -> int:
    dp = [0] * (W + 1)
    for wi, vi in zip(weights, values):
        # CRITICAL: iterate w in REVERSE so dp[w - wi] still refers
        # to the previous item's row, not the current item's row.
        for w in range(W, wi - 1, -1):
            take = dp[w - wi] + vi
            if take > dp[w]:
                dp[w] = take
    return dp[W]

Same O(nW) time, but O(W) space instead of O(nW). The reverse iteration is the textbook DP trick that catches every learner at least once. We dissect why in §6 and again in §11.1.

4.3 Top-Down Memoization

from functools import lru_cache
 
def knapsack_memo(weights: list[int], values: list[int], W: int) -> int:
    n = len(weights)
 
    @lru_cache(maxsize=None)
    def best(i: int, w: int) -> int:
        # Subproblem: best value using items i..n-1 with capacity w.
        if i == n or w == 0:
            return 0
        # Option 1: skip item i
        result = best(i + 1, w)
        # Option 2: take item i (if it fits)
        if weights[i] <= w:
            take = best(i + 1, w - weights[i]) + values[i]
            if take > result:
                result = take
        return result
 
    return best(0, W)

This version recurses from the first unconsidered item forward, which matches the natural problem statement (“starting from item 0, what’s the best I can do with capacity W?”). The cache key is the tuple (i, w); there are at most n × (W+1) distinct keys, so total work is O(nW). See Memoization vs Tabulation for the general technique.

5. Complexity

VariantTimeSpace
2D tabulationO(nW)O(nW)
1D rolling arrayO(nW)O(W)
Top-down memoizationO(nW)O(nW) (cache) + O(n) (recursion stack)
Brute force (no DP)O(2^n)O(n) (recursion stack)

Why O(nW): there are (n+1) × (W+1) = O(nW) table cells; each cell is filled by a constant-time max over two options. Number of states × work per state = O(nW) × O(1) = O(nW). This is the standard DP-cost formula from Memoization vs Tabulation.

Why “pseudo-polynomial”: the running time depends linearly on W, not on log W. The input size (number of bits to encode the problem) is O(n log W) because W is a single integer. So O(nW) = O(n · 2^{log W}) — exponential in input size. For W = 10^9, the DP is 10^{10} operations — infeasible — even though the formal input is tiny. Fully polynomial-time approximation schemes (FPTAS) exist (CLRS Ch. 35.5) that give a (1−ε) approximation in time polynomial in n and 1/ε.

6. Why the 1D Rolling Array Iterates Capacity in Reverse

This is the most-asked-about line in interview DP and deserves its own section.

The 2D recurrence reads dp[i][w] = max(dp[i-1][w], dp[i-1][w - wi] + vi). The cell at row i reads from row i-1 at columns w and w - wi. Both reads are from the previous row.

When we collapse to 1D, the same array dp[] plays both roles: at the moment we are about to write dp[w], its current value still represents row i-1, but as soon as we overwrite it, that slot represents row i. The question is: when we compute dp[w] = max(dp[w], dp[w - wi] + vi), has dp[w - wi] already been overwritten in this iteration of i?

  • If we iterate w in increasing order from 0 to W, then by the time we get to column w, columns 0..w-1 have already been overwritten (they are now the row-i values). Reading dp[w - wi] would give us the current item’s dp[w - wi], allowing item i to be “taken twice” — once at capacity w - wi, then again at capacity w. That’s Unbounded Knapsack (which is a different problem where each item can be picked any number of times, and is in fact the canonical fix: iterate forward to get unbounded behavior).
  • If we iterate w in decreasing order from W down to wi, then by the time we get to column w, columns w+1..W have already been overwritten but columns 0..w are still row-i-1. So dp[w - wi] (which is at a column ≤ w-1) still holds the previous-item value. That preserves the 0/1 semantics: each item is considered at most once per row.

This is the single most famous DP iteration-order issue. Forgetting it produces a correct-looking but semantically wrong program — typically you get an answer that overestimates because items get reused.

7. Reconstructing the Chosen Items

dp[n][W] tells you the maximum value but not which items achieve it. To recover the subset:

def knapsack_with_items(weights, values, W):
    n = len(weights)
    dp = [[0] * (W + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        wi, vi = weights[i - 1], values[i - 1]
        for w in range(W + 1):
            dp[i][w] = dp[i - 1][w]
            if wi <= w and dp[i - 1][w - wi] + vi > dp[i][w]:
                dp[i][w] = dp[i - 1][w - wi] + vi
    # backtrack
    chosen, w = [], W
    for i in range(n, 0, -1):
        if dp[i][w] != dp[i - 1][w]:                # item i was taken
            chosen.append(i - 1)
            w -= weights[i - 1]
    chosen.reverse()
    return dp[n][W], chosen

Backtracking compares dp[i][w] against dp[i-1][w]. If they match, item i was not taken (the optimum was achievable by skipping). If they differ, item i must have been taken — subtract its weight from w and continue. This works only with the 2D table; the 1D rolling array discards the intermediate rows and so cannot reconstruct without extra bookkeeping (one option: keep a separate taken[i][w] boolean array, regaining the O(nW) space).

8. Variants Worth Knowing

8.1 Subset Sum

Given items with weights and a target T, decide if any subset sums to exactly T. Solved by the same DP with dp[i][w] boolean (“can we hit weight exactly w using first i items?”). Recurrence: dp[i][w] = dp[i-1][w] or dp[i-1][w - w_i]. LeetCode 416 (Partition Equal Subset Sum) reduces to this: split the array into two subsets of equal sum iff total is even and a subset sums to total/2.

8.2 Unbounded Knapsack (a.k.a. Coin Change variant)

Each item can be picked any number of times. Iterate the inner loop in forward order on the 1D array — that’s the deliberately-introduced “bug” that makes it work. LeetCode 322 (Coin Change) and LeetCode 518 (Coin Change II) are this family.

8.3 Bounded Knapsack

Each item i has a multiplicity bound c_i (you can take at most c_i copies). Naive: expand into c_i copies of each item and run 0/1 — works but inflates n. Smarter: binary splitting (decompose c_i into 1, 2, 4, ..., r so any count up to c_i is sum of a subset of these, giving O(log c_i) virtual items per real item) or monotonic-deque optimization for O(nW).

8.4 Multidimensional Knapsack

Two (or more) capacity constraints — weight and volume, say. State becomes dp[i][w][v], time and space O(nWV). Common in real packing problems and 2D bin packing reductions.

8.5 Fractional Knapsack

Allow taking fractions of items. Now solvable by a simple greedy: sort items by v_i / w_i (value density), take whole items in that order until a partial item maxes out the capacity. O(n log n). The fact that the fractional version is greedy and the 0/1 version is NP-hard is a beautiful illustration of how a small constraint change (“take whole items only”) can flip a problem’s complexity class entirely.

8.6 Profit-Indexed DP When V Is Small but W Is Huge

If total achievable value V_total is small but W is enormous, swap the roles: dp[i][v] = minimum weight to achieve value at least v using first i items. Time O(n · V_total). This is the basis of the Ibarra-Kim FPTAS for knapsack.

8.7 Meet-in-the-Middle

For n ≈ 40 and large W, split items in half, enumerate all 2^{n/2} subsets of each half (≈ 10^6 each), then combine with sort + binary search. Time O(2^{n/2} log (2^{n/2})) ≈ O(n · 2^{n/2}). Beats DP when W is gigantic but n is moderate.

9. Common Interview Problems

ProblemLeetCode #Pattern
0/1 Knapsack (classic)LC 416 (Partition Equal Subset Sum)Subset-sum reduction
Coin ChangeLC 322Unbounded knapsack
Coin Change 2LC 518Unbounded — count subsets
Target SumLC 494Convert ± signs to subset-sum
Last Stone Weight IILC 1049Min-difference subset partition
Ones and ZeroesLC 4742D-knapsack (two capacities)
Profitable SchemesLC 879Knapsack with two constraints + count

The “knapsack family” is roughly 10% of all DP interview problems.

10. Diagram — Filling the DP Table

flowchart LR
    subgraph Row_i_minus_1
      A0[dp i-1, 0] --> A1[dp i-1, 1]
      A1 --> A2[dp i-1, 2]
      A2 --> A3[dp i-1, w-wi]
      A3 --> Aw[dp i-1, w]
    end
    subgraph Row_i
      B0[dp i, 0] --> B1[dp i, 1]
      B1 --> B2[dp i, 2]
      B2 --> B3[dp i, w-wi]
      B3 --> Bw[dp i, w]
    end
    A3 -- take --> Bw
    Aw -- skip --> Bw

What this diagram shows. Computing one cell dp[i][w] (right edge of bottom row) requires reading two cells from the previous row: dp[i-1][w] (the “skip item i” value, kept as-is) and dp[i-1][w - wi] (the “take item i” value, plus vi). Both reads are from the row above; nothing in row i depends on anything else in row i. That’s why we can collapse to a 1D rolling array — but only if we write row i’s entries in an order that doesn’t clobber the row-i-1 values we still need. Iterating w in decreasing order ensures dp[w - wi] (smaller index) hasn’t been overwritten yet when we read it. Iterating in increasing order overwrites dp[w - wi] first and then reads the new value, which silently turns 0/1 knapsack into Unbounded Knapsack.

11. Pitfalls

11.1 1D Iteration Order Reversed Wrongly

By far the most common interview mistake: writing the 1D rolling-array version with for w in range(W + 1) instead of for w in range(W, wi - 1, -1). The program runs without error and returns a bigger number than the true optimum (because items get re-picked). The bug is invisible on small inputs that happen to not exercise it. Always test on a case where reusing an item would inflate the answer.

11.2 Off-by-One in State Definition

dp[i][w] = “first i items” (so dp[0][*] = 0 is the empty case) is the conventional setup; with n items the answer is dp[n][W]. If you instead define dp[i][w] = “items 0..i” (i.e., 0-indexed inclusive), the answer is dp[n-1][W] and the base case is dp[-1][w] = 0 which is awkward. The “first i” convention is cleaner — pick it and stick with it.

11.3 Forgetting dp[i][0] = 0

Capacity 0 means we can take nothing. This is a base case the table allocation usually handles for free (zero-initialized arrays), but if you change the initialization (e.g., -inf for max-value problems with mandatory-fill semantics) you must remember to override the w=0 column.

11.4 Confusing 0/1 and Unbounded

The two DPs differ by a single character: range(W, wi-1, -1) (0/1) vs range(wi, W+1) (unbounded). When you encounter a knapsack-shaped problem, always re-derive which one it is before coding. Are items distinct physical objects (0/1) or fungible quantities (unbounded)?

11.5 Integer Weights Required

The pseudo-polynomial DP requires integer weights and capacity (so the table indices are well-defined). For real-valued weights, you must scale and round — introducing approximation error. For very precise rational weights, scale to integers via the LCM of denominators, but this can blow up W.

11.6 Treating This as Greedy

Taking items by value-density v_i / w_i is correct for fractional knapsack but fails for 0/1. Counterexample: capacity 10; items (weight 6, value 7) and (weight 5, value 5) plus (weight 5, value 5). Densities: 7/6 ≈ 1.17, 5/5 = 1, 5/5 = 1. Greedy picks the first (value 7), leaving capacity 4 — can’t fit another. Total = 7. But picking both 5-weight items gives value 10. Don’t be fooled into solving 0/1 with greedy.

11.7 Memory Blow-Up

For n = 1000 and W = 10^5, the 2D table is 10^8 integers — gigabytes. Use the 1D rolling array. If you also need to reconstruct items, either store back-pointers as bits (compact) or accept the O(nW) memory.

11.8 Negative Weights or Values

The standard DP assumes positive weights and nonnegative values. Negative values break “skip is always an option” reasoning if items become mandatory; negative weights don’t even make physical sense. If your problem allows them, re-derive the recurrence — it usually still works for nonnegative values + nonnegative weights, but verify base cases.

11.9 LC 416 (Partition Equal Subset Sum) Subtle Reduction

LC 416 asks to partition the array into two equal-sum subsets. The reduction: total sum S must be even, and we need a subset summing to S/2. Then it’s pure subset-sum (boolean knapsack). Many candidates miss the parity check or set the target wrong.

12. Open Questions

  • When does the FPTAS beat the exact DP in practice? Answer: when W is huge but you can tolerate (1 − ε) error; ε = 0.01 is often enough for industrial packing problems.
  • Is there a polynomial-time algorithm for 0/1 Knapsack? No, unless P = NP — Subset Sum (a special case) is NP-complete.
  • Multidimensional knapsack with three or more dimensions becomes intractable quickly; what’s the practical state-of-the-art? Mixed-integer programming solvers like Gurobi or CPLEX with branch-and-cut.

13. See Also

Graph View

Backlinks