The 0/1 Knapsack Problem Explained

Given n items, each with a weight and a value, and a bag that holds a total weight of W: choose a subset with the greatest total value. Each item is taken whole or left behind, hence 0/1.

The problem is worth understanding properly because the shape recurs constantly under other names. Budget allocation, choosing which features fit a release, subset-sum, partitioning a list into two halves of equal sum, all the same recurrence.

Greedy does not work

The tempting approach is to sort by value-to-weight ratio and take items until the bag is full. For the fractional knapsack, where an item can be cut. That is provably optimal. For 0/1 it is not:

W = 10
item A: weight 6,  value 30   ratio 5.0
item B: weight 5,  value 24   ratio 4.8
item C: weight 5,  value 24   ratio 4.8

Greedy takes A first (best ratio), then neither B nor C fits in the remaining 4. Total 30. The optimal answer is B + C: weight 10, value 48.

The reason greedy fails is that taking an item changes which items remain feasible, and no ordering of local decisions accounts for that. You have to compare whole subsets, which is what the recurrence below does without enumerating them.

The recurrence

Define best(i, c) as the greatest value obtainable using items 0..i with capacity c. For each item there are exactly two choices:

best(i, c) = 0                                              if i < 0 or c == 0

best(i, c) = best(i-1, c)                                   if w[i] > c        (cannot fit)

best(i, c) = max( best(i-1, c),                             leave item i
                  v[i] + best(i-1, c - w[i]) )              take item i

That is the whole algorithm. Everything below is the same three lines with progressively less recomputation.

static int naive(int[] w, int[] v, int i, int c) {
    if (i < 0 || c == 0) return 0;
    if (w[i] > c) return naive(w, v, i - 1, c);
    return Math.max(
            naive(w, v, i - 1, c),
            v[i] + naive(w, v, i - 1, c - w[i]));
}

Correct, and O(2ⁿ), every item branches in two. Thirty items is a billion calls.

Memoisation

The exponential blowup is entirely repeated work: the same (i, c) pair is reached along many different paths. Cache it.

static int memo(int[] w, int[] v, int capacity) {
    Integer[][] cache = new Integer[w.length][capacity + 1];
    return solve(w, v, w.length - 1, capacity, cache);
}

private static int solve(int[] w, int[] v, int i, int c, Integer[][] cache) {
    if (i < 0 || c == 0) return 0;
    if (cache[i][c] != null) return cache[i][c];

    int result;
    if (w[i] > c) {
        result = solve(w, v, i - 1, c, cache);
    } else {
        result = Math.max(
                solve(w, v, i - 1, c, cache),
                v[i] + solve(w, v, i - 1, c - w[i], cache));
    }
    return cache[i][c] = result;
}

There are n × (W+1) distinct states and each is computed once, so this is O(nW) time and space. Same recurrence, same answer, a different number of calls.

Bottom-up

The table can be filled directly, which removes the recursion and its stack:

static int knapsack(int[] w, int[] v, int capacity) {
    int n = w.length;
    int[][] dp = new int[n + 1][capacity + 1];

    for (int i = 1; i <= n; i++) {
        for (int c = 0; c <= capacity; c++) {
            dp[i][c] = dp[i - 1][c];                     // leave item i-1
            if (w[i - 1] <= c) {
                dp[i][c] = Math.max(dp[i][c],
                        v[i - 1] + dp[i - 1][c - w[i - 1]]);   // take it
            }
        }
    }
    return dp[n][capacity];
}

Row i is offset by one so dp[0] means “no items”, which removes the negative-index case. Each cell reads only from the row above, which is the observation the next section exploits.

For the example above:

        c=0  1  2  3  4  5  6  7  8  9 10
none      0  0  0  0  0  0  0  0  0  0  0
+A(6,30)  0  0  0  0  0  0 30 30 30 30 30
+B(5,24)  0  0  0  0  0 24 30 30 30 30 54
+C(5,24)  0  0  0  0  0 24 30 30 30 30 48

The last row’s final cell is 48. Note that the 54 in the middle row is not reachable in the final answer: it assumed both A and B, weight 11, which exceeds capacity. Reading the wrong cell is a common mistake; the answer is always dp[n][W].

One dimension

Each row depends only on the previous one, so a single array suffices, and the direction of the inner loop becomes load-bearing:

static int knapsack1D(int[] w, int[] v, int capacity) {
    int[] dp = new int[capacity + 1];

    for (int i = 0; i < w.length; i++) {
        for (int c = capacity; c >= w[i]; c--) {      // DOWNWARD
            dp[c] = Math.max(dp[c], v[i] + dp[c - w[i]]);
        }
    }
    return dp[capacity];
}

The loop must run downwards. Going upward, dp[c - w[i]] would already have been updated for the current item, so the item could be counted twice, which solves a different problem:

// unbounded knapsack: each item may be taken any number of times
for (int c = w[i]; c <= capacity; c++) {
    dp[c] = Math.max(dp[c], v[i] + dp[c - w[i]]);     // UPWARD
}

One loop direction is the entire difference between 0/1 and unbounded. It is worth being able to explain that rather than remembering it, because the two are easy to swap by accident and both produce plausible numbers.

Space drops from O(nW) to O(W). Time is unchanged.

Recovering which items were chosen

The 1D version returns the value and loses the selection. The 2D table keeps it, walk backwards and ask whether each row changed anything:

static List<Integer> chosenItems(int[] w, int[] v, int capacity) {
    int n = w.length;
    int[][] dp = new int[n + 1][capacity + 1];

    for (int i = 1; i <= n; i++) {
        for (int c = 0; c <= capacity; c++) {
            dp[i][c] = dp[i - 1][c];
            if (w[i - 1] <= c) {
                dp[i][c] = Math.max(dp[i][c], v[i - 1] + dp[i - 1][c - w[i - 1]]);
            }
        }
    }

    List<Integer> picked = new ArrayList<>();
    int c = capacity;
    for (int i = n; i > 0; i--) {
        if (dp[i][c] != dp[i - 1][c]) {      // this row improved on the one above: item taken
            picked.add(i - 1);
            c -= w[i - 1];
        }
    }
    Collections.reverse(picked);
    return picked;
}

If dp[i][c] equals dp[i-1][c], item i-1 contributed nothing at this capacity and was left out. Otherwise it was taken, so subtract its weight and continue. Ties are resolved arbitrarily, which is fine. There can be several optimal subsets.

What O(nW) actually costs

This is where the classification surprises people. O(nW) looks polynomial and is not: the input size is n items plus log W bits to write down the capacity, so the running time is exponential in the length of W.

A capacity of one billion with thirty items is thirty billion cells, the algorithm is pseudo-polynomial, and 0/1 knapsack is NP-hard, the table only feels efficient when W is small.

Practical consequences:

• Scale the units. Weights in whole grams rather than milligrams shrinks W by a thousand. If weights are decimals, multiply everything to integers first, the algorithm needs integer indices.
• Watch memory. int[100][1_000_001] is roughly 400 MB. The 1D version is 4 MB.
• When W is genuinely huge, drop exactness: a greedy solution plus local search, or an FPTAS that rounds values to trade a bounded error for tractable time.

Related shapes

Recognising these as the same recurrence is most of the value:

• Subset sum, is there a subset totalling exactly S? Knapsack with value == weight, asking whether dp[S] == S.
• Equal partition, split into two equal-sum halves. Subset sum for total / 2, impossible when the total is odd.
• Coin change (minimum coins), unbounded knapsack minimising count rather than maximising value.
• Bounded knapsack, at most k copies of an item. Expand into k copies, or better, use the binary trick: copies of size 1, 2, 4, … which represents any count up to k in log k items.

Frequently asked questions

Why does greedy by value-to-weight ratio fail?

Because taking one item changes what still fits. Greedy is optimal for the fractional knapsack, where items can be cut, and provably not for 0/1.

What is the time complexity?

O(nW) for the dynamic programming solutions, and O(2ⁿ) for naive recursion. O(nW) is pseudo-polynomial, not polynomial.

Why must the 1D loop iterate downwards?

Going upward reads cells already updated for the current item, allowing it to be used more than once, which solves the unbounded knapsack instead.

How do I get the list of chosen items?

Keep the 2D table and walk back from dp[n][W]: whenever a row differs from the one above it, that item was taken.

Memoisation or bottom-up?

Same complexity. Memoisation follows the recurrence and only visits reachable states; bottom-up avoids recursion depth and allows the 1D space optimisation. Bottom-up is usually preferred in production.

Why is O(nW) not polynomial?

W is written in log W bits, so the running time is exponential in the input’s length. That is what pseudo-polynomial means, and it is why the problem is NP-hard.

What if weights are decimals?

Scale everything to integers first, the capacity indexes an array. Choose the coarsest unit the problem tolerates, since W drives both time and memory.

How does this relate to subset sum?

Subset sum is knapsack with each item’s value equal to its weight, asking whether the best value for capacity S equals S.

What about taking at most k copies of an item?

Bounded knapsack. Expanding into k copies works; splitting into powers of two (1, 2, 4, …) does it in log k items instead.

What if the capacity is enormous?

Exact DP stops being viable. Use an approximation: greedy plus local search, or an FPTAS that rounds values for a bounded error.

Where should I go next?

The algorithms guides cover related problems, and Java ArrayList covers the collection these implementations return.