0/1 Knapsack (DP)

Intuition

You are packing a carry-on bag with a strict weight limit and a pile of gadgets, each with a weight and a usefulness score. Grabbing the most useful items first can fail: one heavy, valuable item might crowd out two lighter ones that are worth more together. Trying every subset works but costs 2 to the power n. Dynamic programming notices that the only thing that matters about the decisions made so far is how much capacity is left, so it solves each (items considered, capacity left) pair once.

For each item there are only two choices, which is where the 0/1 in the name comes from: skip it and keep the best value without it, or take it, gaining its value but losing its weight from the remaining capacity. The answer for a state is the better of those two choices.

How it works step by step

1. Define dp[i][w] as the best value using only the first i items with capacity w.
2. Base case: dp[0][w] = 0 for every w, since no items means no value.
3. Recurrence: dp[i][w] = dp[i-1][w] (skip item i). If weight[i] <= w, also consider dp[i-1][w - weight[i]] + value[i] (take it) and keep the maximum.
4. Fill rows top to bottom; within a row the order of w does not matter in the 2D version because every read comes from row i-1.
5. The answer is dp[n][W]. To list the chosen items, walk back from (n, W): if dp[i][w] != dp[i-1][w], item i was taken, so subtract its weight.
6. Space optimisation: keep one array dp[w] and for each item loop w from W down to weight[i]. Going backwards means dp[w - weight[i]] still holds the previous row's value.

Dry run of the 2D table

Items as (weight, value): item 1 = (1, 15), item 2 = (3, 20), item 3 = (4, 30). Capacity 4. Each row of the table below is one row of dp, listing values for capacities 0 to 4.

The greedy choice of the single most valuable item (item 3, value 30) loses to the pair worth 35, which is exactly the trap the table avoids. Now watch what goes wrong if you loop forward in the 1D version: processing item 1 with w increasing sets dp[1] = 15, then dp[2] = dp[1] + 15 = 30, which takes item 1 twice. Looping backwards reads dp[1] before it is updated, so each item is used at most once.

Code

public class Knapsack {
    // 1D 0/1 knapsack: O(n * W) time, O(W) space.
    public static int maxValue(int[] weight, int[] value, int capacity) {
        int[] dp = new int[capacity + 1];
        for (int i = 0; i < weight.length; i++) {
            // Backwards so dp[w - weight[i]] still refers to the previous item row.
            for (int w = capacity; w >= weight[i]; w--) {
                dp[w] = Math.max(dp[w], dp[w - weight[i]] + value[i]);
            }
        }
        return dp[capacity];
    }

    public static void main(String[] args) {
        System.out.println(maxValue(new int[]{1, 3, 4}, new int[]{15, 20, 30}, 4)); // 35
    }
}

def knapsack(weights, values, capacity):
    """2D table so we can also recover which items were chosen."""
    n = len(weights)
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        wt, val = weights[i - 1], values[i - 1]
        for w in range(capacity + 1):
            dp[i][w] = dp[i - 1][w]                       # skip item i
            if wt <= w:
                dp[i][w] = max(dp[i][w], dp[i - 1][w - wt] + val)   # take it

    chosen, w = [], capacity
    for i in range(n, 0, -1):
        if dp[i][w] != dp[i - 1][w]:                       # value changed: item taken
            chosen.append(i - 1)
            w -= weights[i - 1]
    return dp[n][capacity], chosen[::-1]


print(knapsack([1, 3, 4], [15, 20, 30], 4))   # (35, [0, 1])
print(knapsack([5], [10], 4))                 # (0, [])

Time and space complexity

O(n x W) is called pseudo-polynomial: it is polynomial in the numeric value of the capacity, not in the number of bits needed to write it. Double the number of digits in W and the table grows exponentially, which is why knapsack is still NP-hard in general and why huge capacities with few items call for a different approach.

Edge cases

• Capacity 0: the answer is 0 unless the problem allows zero-weight items.
• Item heavier than the capacity: the take branch never applies, and the 1D inner loop simply does not run.
• Zero-weight items: the backwards loop still takes each one exactly once; a forward loop would add it infinitely in the unbounded sense.
• Exact-fill variants: when the bag must be filled exactly, initialise unreachable capacities to negative infinity instead of 0.
• Large values: the sum of values can overflow int; use long if values and counts are large.

Common mistakes

• Iterating capacity upwards in the 1D version, which silently turns 0/1 knapsack into unbounded knapsack.
• Swapping the loops in the 1D version (capacity outer, items inner). That counts combinations differently and is a bug for 0/1.
• Mixing 0-based item arrays with a 1-based dp table and reading weights[i] instead of weights[i - 1].
• Trying to reconstruct the chosen items from the 1D array; the history has been overwritten. Keep the 2D table if you need them.
• Sorting by value-to-weight ratio and picking greedily. That is only correct for the fractional version.

Variations and when to use it

Recognise knapsack whenever a problem says choose a subset under a budget, or can these numbers be split to hit a target. Subset sum and partition equal subset sum are knapsack with booleans instead of values. Counting variants such as Target Sum replace max with addition. Unbounded knapsack, where each item can be reused, is the same 1D loop run forwards, and Coin Change is its best-known form. Fractional knapsack, where items can be cut, is solved greedily by value per unit weight in O(n log n) and needs no DP at all. Two-dimensional budgets such as Ones and Zeroes add a second capacity axis. The take-or-skip pattern also appears in Longest Common Subsequence, where each step decides whether to consume a character.

Related LeetCode problems

• #416 Partition Equal Subset Sum — boolean knapsack with capacity equal to half the total sum.
• #494 Target Sum — counting knapsack after rewriting the plus and minus signs as a subset with a fixed sum.
• #1049 Last Stone Weight II — find the subset sum closest to half the total.
• #474 Ones and Zeroes — 0/1 knapsack with two capacities, zeros and ones, both looped backwards.
• #322 Coin Change — the unbounded variant, minimising item count with a forward loop.
• #518 Coin Change II — unbounded counting; loop order decides combinations versus permutations.
• #198 House Robber — the same take-or-skip recurrence, with adjacency instead of weight as the constraint.

FAQ