Dynamic Programming8 min read

0/1 Knapsack

Pack a suitcase for maximum value — each item is all-or-nothing
time:Pseudo-poly · \(O(n·W)\)space:\(O(n·W)\) or \(O(W)\)each item:take it or leave it

Imagine you're packing a suitcase for a trip. You have a list of items — each with a weight and a value — and your bag can hold at most W kilograms. The catch: you either pack an item whole or leave it behind. You can't take half a jacket or a quarter of a laptop. That's the 0/1 Knapsack problem.

The "0/1" just means each item has two states: 0 (left behind) or 1 (packed). No fractions, no splitting.

Why Greedy Doesn't Work Here

Your instinct might be: take the item with the best value-per-kilo ratio first, then the next best, and so on. That's the greedy approach — but it fails here. Taking the best-ratio item might leave awkward remaining space that only fits cheap filler (contrast this with Fractional Knapsack, where splitting items eliminates wasted space). The items interact — and DP handles those interactions exactly.

The Big Idea: Include or Exclude

Define dp[i][w] = maximum value you can pack using the first i items and weight limit w. For each item, you face exactly two choices:

Leave item i out: dp[i][w] = dp[i-1][w] — same as best without this item.

Pack item i (only if it fits, i.e. wt[i] ≤ w): dp[i][w] = dp[i-1][w - wt[i]] + val[i].

You take whichever choice is larger. Base cases: dp[0][w] = 0 for all w (no items = no value), dp[i][0] = 0 for all i (zero capacity = nothing fits).

Space Optimization to 1D

Notice dp[i][w] only ever looks at the row above it (row i-1). So you can collapse the 2D table into a single 1D array. But here's the catch: you must iterate weight from W down to wt[i]. If you went left-to-right, you'd accidentally let item i contribute to itself — using it multiple times. Right-to-left keeps each item to exactly one use.

Reconstructing What You Packed

The final dp[n][W] tells you the maximum value. To find out which items you packed, trace back through the full 2D table from cell (n, W): if dp[i][w] differs from dp[i-1][w], item i was included — subtract its weight and move up. Otherwise, item i was skipped — just move up. Reconstruction requires the full 2D table, not just the last row.

Note: The 0/1 Knapsack is called 'pseudo-polynomial' because \(O(n·W)\) looks polynomial but W can be astronomically large in binary — making the problem NP-hard in theory, yet fast in practice for reasonable W.

0/1 Knapsack — 1D space-optimized

def knapsack(weights, values, W):
    dp = [0] * (W + 1)
    for w, v in zip(weights, values):
        for cap in range(W, w - 1, -1):  # right to left!
            dp[cap] = max(dp[cap], dp[cap - w] + v)
    return dp[W]


weights = [2, 3, 4, 5]
values  = [3, 4, 5, 6]
print(knapsack(weights, values, 8))  # 10
Output
10

Complexity

⏱️ Time
n items × W+1 capacity values — fast when W is reasonable
Pseudo-polynomial \(O(n·W)\)
📊 Space (2D table)
Required if you want to reconstruct which items were packed
Full table \(O(n·W)\)
🪄 Space (1D optimized)
Iterate capacity right-to-left; loses reconstruction ability
Single row \(O(W)\)
🔍 Item reconstruction
Walk backwards through the 2D table — \(O(n)\) rows, \(O(W)\) steps
Trace-back \(O(n + W)\)
🐌 Brute force (all subsets)
DP's \(O(n·W)\) is exponentially better when W is manageable
Exponential \(O(2^n)\)

Quick check

Why must the inner loop go from W down to wt[i] (right to left) in the 1D version?

Continue reading