0/1 knapsack

You’ll recognise it when

• You pick a subset of items, and each item can be used at most once.
• There’s a hard limit on the total: weight, cost, time, a target sum.
• You maximise a value, or ask whether a total is reachable, or count how many subsets reach it.
• The limit is an integer small enough to index an array with, say up to 10⁵.

If each item can be reused as often as you like (coins, for example), it’s the unbounded knapsack instead. The table is the same idea with one change, see Variations.

The idea

You’re packing a bag that holds 7 kg. Each item has a weight and a value, and you want the most value that fits. Trying every subset works for 4 items (16 subsets) but not for 40 (a trillion).

Instead, look at the items one at a time and answer a smaller question first: with only the first i items and room c, what’s the best value? For item i there are just two choices. Skip it, and the answer is whatever the first i - 1 items managed with the same room. Take it, and you gain its value but have w less room for the earlier items, whose best for that smaller room you’ve already worked out. Keep the better of the two.

How it works

Build a table with one row per item (plus a row 0 for “no items”) and one column per capacity from 0 to W. dp[i][c] is the best value using only the first i items with room c. The graphic fills it row by row as you scroll.

Why it’s correct: every subset of the first i items either leaves item i out or puts it in. The best subset that leaves it out is dp[i-1][c]; the best that puts it in is item i plus the best subset of the others that fits in c - w, which is dp[i-1][c-w]. Both cells are in the row above, already final, so every cell is right once the row above is.

def knapsack(items, capacity):
    """items is a list of (weight, value). Returns (best value, chosen item indices)."""
    n = len(items)
    # dp[i][c] = best value using only the first i items, with capacity c
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        w, v = items[i - 1]
        for c in range(capacity + 1):
            dp[i][c] = dp[i - 1][c]
            if w <= c and dp[i - 1][c - w] + v > dp[i][c]:
                dp[i][c] = dp[i - 1][c - w] + v

    # Walk back from the bottom-right corner to see which items were taken.
    chosen, c = [], capacity
    for i in range(n, 0, -1):
        if dp[i][c] != dp[i - 1][c]:
            chosen.append(i - 1)
            c -= items[i - 1][0]
    chosen.reverse()
    return dp[n][capacity], chosen

#include <algorithm>
#include <utility>
#include <vector>
using namespace std;

// items holds {weight, value}. Returns {best value, chosen item indices}.
pair<long long, vector<int>> knapsack(const vector<pair<int, long long>>& items, int capacity) {
    int n = items.size();
    // dp[i][c] = best value using only the first i items, with capacity c
    vector<vector<long long>> dp(n + 1, vector<long long>(capacity + 1, 0));
    for (int i = 1; i <= n; i++) {
        auto [w, v] = items[i - 1];
        for (int c = 0; c <= capacity; c++) {
            dp[i][c] = dp[i - 1][c];
            if (w <= c && dp[i - 1][c - w] + v > dp[i][c]) {
                dp[i][c] = dp[i - 1][c - w] + v;
            }
        }
    }

    // Walk back from the bottom-right corner to see which items were taken.
    vector<int> chosen;
    int c = capacity;
    for (int i = n; i >= 1; i--) {
        if (dp[i][c] != dp[i - 1][c]) {
            chosen.push_back(i - 1);
            c -= items[i - 1].first;
        }
    }
    reverse(chosen.begin(), chosen.end());
    return {dp[n][capacity], chosen};
}

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

class Knapsack {
    // Returns the best value; the indices of the chosen items go into `chosen`.
    static long solve(int[] weight, long[] value, int capacity, List<Integer> chosen) {
        int n = weight.length;
        // dp[i][c] = best value using only the first i items, with capacity c
        long[][] dp = new long[n + 1][capacity + 1];
        for (int i = 1; i <= n; i++) {
            int w = weight[i - 1];
            long v = value[i - 1];
            for (int c = 0; c <= capacity; c++) {
                dp[i][c] = dp[i - 1][c];
                if (w <= c && dp[i - 1][c - w] + v > dp[i][c]) {
                    dp[i][c] = dp[i - 1][c - w] + v;
                }
            }
        }

        // Walk back from the bottom-right corner to see which items were taken.
        int c = capacity;
        for (int i = n; i >= 1; i--) {
            if (dp[i][c] != dp[i - 1][c]) {
                chosen.add(i - 1);
                c -= weight[i - 1];
            }
        }
        Collections.reverse(chosen);
        return dp[n][capacity];
    }
}

The code looks only at row i - 1 while filling row i, so one array of size W + 1 is enough. The catch: loop c downward. Going down, dp[c - w] hasn’t been touched for this item yet, so it still means “without item i”. Going up, it may already include item i, and the item gets taken twice.

dp = [0] * (W + 1)
for w, v in items:
    for c in range(W, w - 1, -1):   # downward: each item at most once
        dp[c] = max(dp[c], dp[c - w] + v)

You lose the traceback with one row, so keep the full table when you need the chosen items.

Why it’s O(n·W)

There are (n + 1) × (W + 1) cells and each takes one comparison, so time is O(n·W). The walk back is O(n). The table takes O(n·W) memory; the one-row version takes O(W).

That looks polynomial but isn’t quite. W is a number in the input, written with about log₂ W digits, and the running time grows with its value. Add ten bits to W and the table gets 1,000 times wider. That’s called pseudo-polynomial. Knapsack is NP-hard, and this doesn’t contradict that: with W = 10¹² the table is hopeless.

Common mistakes

for c in range(w, W + 1):           # ✗ reuses the item
for c in range(W, w - 1, -1):       # ✓ each item at most once

for c in range(w, W + 1): ...       # ✗ dp[i][c] for c < w stays 0
for c in range(W + 1):              # ✓ copy first, then try taking
    dp[i][c] = dp[i - 1][c]

Variations

• Unbounded knapsack and coin change. Each item may be used any number of times. Take from the same row: dp[i][c-w] + v. In one row, loop c upward. Minimum coins for an amount uses min and a start of 0 at dp[0].
• Subset sum and equal partition. Values don’t matter, only whether a total is reachable: dp[c] = dp[c] or dp[c - w]. To split an array into two equal halves, check whether total / 2 is reachable (and give up if the total is odd).
• Counting subsets. Replace max with +: dp[c] += dp[c - w], starting from dp[0] = 1. Target Sum reduces to this.
• One-row space optimisation. O(W) memory, loop capacity downward, as shown after the code. Keep the table if you need to list the chosen items.
• Big capacity, small values. Swap the roles: dp[v] is the smallest weight that achieves value v, then take the largest v whose weight fits. That’s O(n · total value).