0/1 Knapsack0/1 knapsack

01Why it exists

Reach for it when you see:Each item is in or out, nothing can be split, a weight or budget cap, maximise the total value, hit a target sum exactly, split into two piles with the smallest gap, capacity is a smallish integer.

02The core idea

Each of the n items is either taken or left, so there are 2ⁿ combinations; at n = 40 that is a trillion of them to enumerate. Greedy does not work either. In the interactive demo D has the best value-to-weight ratio at 7/5 = 1.4, but taking D first leaves room for only 2, so all you can add is A, for a total value of 8 — while the optimum is B + C = 9, both with lower ratios. Items cannot be split, so a high-ratio item can block the space a better pair would use. That is the fundamental difference between the 0/1 knapsack and the fractional knapsack, where you may take part of an item and being greedy by ratio is correct. The DP defines the state dp[i][w] = the best value considering only the first i items at capacity w, and then asks one question about item i: take it or not?

The recurrence is dp[i][w] = max(dp[i−1][w], dp[i−1][w−wᵢ] + vᵢ), where the second term exists only when w ≥ wᵢ. Why it is correct: take any optimal solution for (i, w). Either it leaves out item i, in which case it is a solution for the first i−1 items at capacity w, and it must be an optimal one — otherwise swapping in a better set would improve (i, w) too, a contradiction. Or it contains item i, and removing i leaves an optimal solution for the first i−1 items at capacity w−wᵢ, by the same argument. That is optimal substructure. Every subset falls into one of those two cases, so taking the max compares all 2ⁿ combinations while visiting only (n+1)(W+1) distinct subproblems. The table stores values alone; to find out which items were chosen, walk back from dp[n][W], where dp[i][w] ≠ dp[i−1][w] means this cell had to take item i — record it, subtract wᵢ from the capacity, and move up a row.

The table has (n+1)(W+1) cells and each takes O(1), so the time is O(nW), and the whole table gets filled whatever the input looks like. The 2-D table costs O(nW) space too, but row i only reads row i−1, so keep a single array of length W+1 and scan w downward from W to wᵢ: dp[w] = max(dp[w], dp[w−wᵢ] + vᵢ). Going downward means dp[w−wᵢ] has not been overwritten yet this round, so it still holds the previous row's value. Space drops to O(W), at the price of no longer being able to trace back what was chosen. Note that O(nW) is pseudo-polynomial: W is a number inside the input, not the length of the input, so one more digit on W makes the table ten times bigger, and a capacity of 10⁹ puts the method out of reach entirely. If the total value happens to be small in that case, swap the two dimensions and let dp[v] = the smallest weight that reaches a total value of v.

The most common mistake is scanning w upward in the 1-D version: dp[w−wᵢ] has already been updated this round and already includes item i, so the same item goes in several times and the algorithm quietly becomes the unbounded knapsack of the next lesson. The second is initialisation. For "the best value within capacity W", initialise everything to 0; for "fill W exactly", set only dp[0] = 0 and make the rest −∞ to mark it unreachable. Changing how the same table combines values gives you other problems: replace max with or and it answers "can some subset sum to s", the subset-sum problem; replace it with addition and set dp[0] = 1 and it counts how many ways there are. Compared with House Robber from 1-D DP, the knapsack state carries one extra dimension, the remaining capacity — the usual way to describe a limited resource.

03The algorithm

1. 1Confirm the shape of the problem: each item can be taken at most once, there is an integer capacity W, and the goal is to maximise the total value (or decide whether a sum is reachable, or count the ways). Items that can be taken any number of times make it an unbounded knapsack.
2. 2Define dp[i][w] = the best value from the first i items at capacity w. Base case: row 0 is all zeros (when the capacity must be filled exactly, only dp[0][0] = 0 and the rest is −∞).
3. 3Outer loop i from 1 to n, inner loop w from 0 to W: start with dp[i][w] = dp[i−1][w] (skip it), and if w ≥ wᵢ, take the larger of that and dp[i−1][w−wᵢ] + vᵢ (take it).
4. 4The answer is dp[n][W]. To list what was chosen, walk upward from (n, W): whenever dp[i][w] ≠ dp[i−1][w], record item i and set w −= wᵢ; otherwise leave w alone. Stop at row 0.
5. 5When only the best value matters, roll the table into a single row: a 1-D dp of length W+1, items on the outside, w scanned downward from W to wᵢ, dp[w] = max(dp[w], dp[w−wᵢ] + vᵢ).
6. 6Other variants change only the combining step and the initial values: or with can[0] = True for feasibility, addition with ways[0] = 1 for counting. The loop structure stays exactly the same.

04Interactive demo

Four items — A (weight 1, value 1), B (weight 3, value 4), C (weight 4, value 5), D (weight 5, value 7) — and a capacity of 7. The table fills one cell at a time: blue is the cell being computed, yellow is the "skip it" source dp[i−1][w], and green is the "take it" source dp[i−1][w−wᵢ]. Once it is full, the traceback runs upward from the bottom-right corner; the green path marks the cells it walks through, and in the item row green means taken while a strikethrough means left behind. Watch the final cell dp[4][7]: taking D, the item with the best ratio, only reaches 8, while leaving it out keeps B + C = 9.

05Code

Three functions: the 2-D table with traceback (the only one that can list which items were chosen), the rolled-up 1-D version scanning downward (the standard form when only the best value is needed), and the boolean knapsack for the smallest gap between two piles. The 2-D version is the easiest to follow and the only one that traces back; the 1-D version is what you actually write when solving problems. The C++ boolean knapsack uses std::bitset, where the single line can |= can << x performs a whole pass and handles 64 bits at a time.

def knapsack_table(weights, values, cap):
    """2-D table: dp[i][w] = best value from the first i items with capacity w. O(nW)"""
    n = len(weights)
    dp = [[0] * (cap + 1) for _ in range(n + 1)]   # row 0: no items yet, so all zeros
    for i in range(1, n + 1):
        wt, val = weights[i - 1], values[i - 1]
        for w in range(cap + 1):
            dp[i][w] = dp[i - 1][w]                  # skip item i
            if w >= wt:                              # only consider taking it if it fits
                dp[i][w] = max(dp[i][w], dp[i - 1][w - wt] + val)

    # Traceback: a cell that differs from the row above means item i was taken
    chosen, w = [], cap
    for i in range(n, 0, -1):
        if dp[i][w] != dp[i - 1][w]:
            chosen.append(i - 1)
            w -= weights[i - 1]
    return dp[n][cap], chosen[::-1]


def knapsack(weights, values, cap):
    """Rolled into one row. O(W) space"""
    dp = [0] * (cap + 1)
    for wt, val in zip(weights, values):
        for w in range(cap, wt - 1, -1):             # downward: dp[w - wt] is still the previous row
            dp[w] = max(dp[w], dp[w - wt] + val)     # upward would take the same item twice
    return dp[cap]


def min_split_diff(nums):
    """Two piles with the smallest gap: boolean knapsack, weight is the value, capacity is half the total"""
    total = sum(nums)
    half = total // 2
    can = [True] + [False] * half                    # can[s]: does some subset add up to exactly s?
    for x in nums:
        for s in range(half, x - 1, -1):             # downward again, so each number is used once
            can[s] = can[s] or can[s - x]
    best = max(s for s in range(half + 1) if can[s])
    return total - 2 * best                          # one pile is best, the other is total - best


if __name__ == "__main__":
    weights, values = [1, 3, 4, 5], [1, 4, 5, 7]     # A, B, C, D, same as the interactive demo
    print(knapsack_table(weights, values, 7))  # (9, [1, 2]): take B and C
    print(knapsack(weights, values, 7))        # 9
    print(min_split_diff([2, 7, 4, 1, 8, 1]))  # 1 (11 against 12)
    print(min_split_diff([1, 5, 11, 5]))       # 0 (splits evenly)

06Practice

• LeetCode 416Partition Equal Subset Sum (boolean knapsack, capacity is half the total)Medium
• LeetCode 1049Last Stone Weight II (really the smallest gap between two piles)Medium
• LeetCode 494Target Sum (turns into counting subset sums)Medium
• LeetCode 2915Length of the Longest Subsequence That Sums to Target (exact fill, initialise to −∞)Medium
• LeetCode 474Ones and Zeroes (a knapsack with two capacities)Medium
• LeetCode 879Profitable Schemes (counting with a minimum profit)Hard