Knapsack & Subset-Sum DP — Algorithms Course

What you'll learn

The 0/1 knapsack is the gateway to two-dimensional DP — and to a whole family of problems (subset sum, partition, and more) that share its table. The state now needs two indices: which items, and how much capacity.

By the end you'll be able to:

Set up the item × capacity DP table
Write the "skip or take" transition
Recognize subset sum and partition as the same DP
Reduce the table to a single rolling row

0/1 knapsack

You have a knapsack of capacity W and items with weights and values; each item is taken whole or not at all. Maximize the value carried. Unlike the fractional version (Module 14), greedy fails here — you must weigh every combination, which is exactly what the table does.

The 2-D table

Let dp[i][w] be the best value using the first i items within capacity w. For each cell you choose the better of two already-computed cells above it: skip item i (dp[i-1][w]) or take it (value + dp[i-1][w - weight]). Watch the table fill row by row:

0/1 knapsack table

0/1 knapsack (capacity 5)

i\w

∅

dp[i][w] = max(skip, value[i] + dp[i-1][w-wt])

computing depends on answer

1/200/1 knapsack, capacity 5. Items: i1(w1,v6) i2(w2,v10) i3(w3,v12). Row ∅ (no items) is all 0.

Each cell picks the better of skipping the item (directly above) or taking it (value + a cell up and to the left).

In code

Language

knapsack.py

def knapsack(weights, values, capacity):
    n = len(weights)
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        for w in range(capacity + 1):
            dp[i][w] = dp[i - 1][w]                    # skip item i
            if weights[i - 1] <= w:                    # or take it
                dp[i][w] = max(dp[i][w],
                               values[i - 1] + dp[i - 1][w - weights[i - 1]])
    return dp[n][capacity]

Tip

Because row i depends only on row i-1, you can collapse the table to a single 1-D array of size W+1 — iterating w from high to low so each item is used at most once. That's the standard O(nW) time, O(W) space solution.

The subset-sum family

Subset sum: can any subset hit an exact target? Same table, but dp[i][w] is a boolean "is w reachable with the first i items?"
Partition: can the set be split into two equal-sum halves? That's subset sum for target total / 2.
Unbounded knapsack: unlimited copies of each item — take it from the current row (dp[i][w - weight]) instead of the row above, so an item can repeat.

Key idea

The knapsack table is O(nW) — pseudo-polynomial, because W can be exponential in its number of bits. It's fast when W is modest, which is why 0/1 knapsack is a favorite DP even though the general problem is NP-hard (Module 35).

Recap & quick check

Key takeaways

0/1 knapsack takes each item whole or not — greedy fails, DP wins.
State dp[i][w] = best value with first i items within capacity w.
Transition: max(skip = dp[i-1][w], take = value + dp[i-1][w - weight]).
Subset sum and partition are the same table with a boolean state.
Collapse to a 1-D rolling array for O(W) space; time is O(nW), pseudo-polynomial.

Quick check

1. What does dp[i][w] represent in 0/1 knapsack?

2. The transition for taking item i uses which cell?

3. Partition into two equal halves reduces to:

4. Why is knapsack called 'pseudo-polynomial'?

Next, DP that compares and transforms sequences — the algorithms behind diff and spell-check. Next up: Module 18 — Dynamic Programming on Sequences.