DP — Knapsack

TL;DR

Knapsack is choice DP: walk the items one at a time, and for each item make a single decision — include it or skip it. The state is the remaining budget (capacity, target sum, number of zeros and ones, …), and the answer at capacity c is built from the answer at capacity c - w after subtracting this item’s cost. That’s the whole pattern.

Two flavors cover almost every variant. 0/1 knapsack lets you use each item at most once — the 1D space-optimized loop iterates capacity backwards so the value at dp[c - w] still reflects “this item not yet used”. Unbounded knapsack lets you reuse items freely — same skeleton, but you iterate capacity forwards so dp[c - w] already includes this item and the recurrence picks it up again.

The same two skeletons answer a surprising number of LeetCode problems: partition-equal-subset (LC 416), target-sum (LC 494), coin-change-ii (LC 518), coin-change (LC 322), and ones-and-zeroes (LC 474, two simultaneous capacities). Once you can write the 1D version from memory and you know which direction to loop capacity, you’re done.

When to reach for it

Signals that the problem is knapsack:

• There is a limited budget — capacity W, target sum T, a coin amount, a count of zeros and ones — and a list of items each consuming some of that budget.
• Each item has a weight/cost and either a value to maximise or just contributes to a feasibility/count question.
• The question is shaped like “can we hit target T using a subset of these items?”, “how many subsets sum to T?”, or “max value within budget W?”.
• A greedy attempt fails because picking the locally-best item leaves a worse remainder. Greedy does work for fractional knapsack — that’s not DP, that’s “sort by value/weight”. If items are indivisible, you’re in 0/1 territory.

If the items can be picked in any order and quantity (coins, repeated jobs), it’s unbounded. If each item is unique (a stone, a paper-target pair), it’s 0/1.

Flavor 1 — 0/1 knapsack

Each item used at most once. Maximise total value subject to total weight ≤ capacity.

def knapsack_01_2d(weights: list[int], values: list[int], W: int) -> int:
    n = len(weights)
    dp = [[0] * (W + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        w, v = weights[i - 1], values[i - 1]
        for c in range(W + 1):
            dp[i][c] = dp[i - 1][c]                 # skip item i
            if c >= w:
                dp[i][c] = max(dp[i][c], dp[i - 1][c - w] + v)  # take it
    return dp[n][W]

The 2D form makes the recurrence obvious: row i is built from row i - 1. But you only need one row, because every read is from the previous row at index c or c - w. If you iterate c from high to low, dp[c - w] still holds the previous row’s value when you read it — exactly what 0/1 needs.

def knapsack_01(weights: list[int], values: list[int], W: int) -> int:
    dp = [0] * (W + 1)
    for w, v in zip(weights, values):
        for c in range(W, w - 1, -1):   # reverse: don't reuse item
            dp[c] = max(dp[c], dp[c - w] + v)
    return dp[W]

Worked example. Items (weight, value) = [(2,3), (3,4), (4,5), (5,6)], capacity W = 5.

Start: dp = [0, 0, 0, 0, 0, 0] (indices 0..5).

After item (2, 3) — loop c from 5 down to 2, set dp[c] = max(dp[c], dp[c-2] + 3):

After item (3, 4) — loop c from 5 down to 3:

dp[5] = max(3, dp[2] + 4) = max(3, 7) = 7 — items (2,3) + (3,4) exactly fill capacity 5.

After item (4, 5) — loop c from 5 down to 4:

dp[4] = max(4, dp[0] + 5) = 5. dp[5] = max(7, dp[1] + 5) = 7 — staying with the previous combo.

After item (5, 6) — loop c = 5 only:

dp[5] = max(7, dp[0] + 6) = 7. Answer: 7, achieved by items 1 and 2.

Notice why the loop runs backwards. When we read dp[c - w] at c = 5, w = 3, we want the value before item (3, 4) was considered. Going high-to-low guarantees dp[2] is still the old 3, not a freshly-updated value that already includes this item.

Flavor 2 — unbounded knapsack (Coin Change II)

LC 518: given coin denominations and an amount, count the number of distinct ways to make that amount. Each coin is reusable.

def change(amount: int, coins: list[int]) -> int:
    dp = [0] * (amount + 1)
    dp[0] = 1                       # one way to make 0: pick nothing
    for coin in coins:
        for c in range(coin, amount + 1):   # forward: allow reuse
            dp[c] += dp[c - coin]
    return dp[amount]

The forward loop is the whole trick. When we update dp[c] += dp[c - coin], dp[c - coin] has already been updated in this same pass — meaning it represents “ways to make c - coin using coins up to and including this one”, so reusing is automatic.

Worked example. coins = [1, 2, 5], amount = 5.

Start: dp = [1, 0, 0, 0, 0, 0].

After coin 1 — dp[c] += dp[c-1] for c = 1..5:

Only one way to make any amount with just 1s.

After coin 2 — dp[c] += dp[c-2] for c = 2..5:

dp[2] = 1 + dp[0] = 2 (two 1s, or one 2). dp[4] = 1 + dp[2] = 3 (1+1+1+1, 1+1+2, 2+2). dp[5] = 1 + dp[3] = 3.

After coin 5 — dp[c] += dp[c-5] for c = 5..5:

dp[5] = 3 + dp[0] = 4. Answer: 4 — {1×5}, {1×3 + 2}, {1 + 2×2}, {5}.

Flavor 3 — partition-style (LC 416)

Can we partition nums into two subsets with equal sum? Total sum S must be even, and we ask: is there a subset summing to S / 2? That’s 0/1 knapsack with item weight = value = nums[i], capacity S / 2, asking for feasibility instead of max value.

def can_partition(nums: list[int]) -> bool:
    s = sum(nums)
    if s % 2:
        return False
    target = s // 2
    dp = [False] * (target + 1)
    dp[0] = True
    for x in nums:
        for c in range(target, x - 1, -1):   # reverse: 0/1 semantics
            dp[c] = dp[c] or dp[c - x]
    return dp[target]

Same pattern: reverse loop, single-pass per item, dp[0] = True as the empty-subset base case. Target Sum (LC 494) is the same trick — count subsets with sum (S + target) / 2 — and Ones and Zeroes (LC 474) is 0/1 knapsack with two simultaneous capacities (m zeros, n ones), so you carry a 2D dp[i][j] and reverse-loop both axes.

Why it works — the invariant

After processing the first i items, dp[c] holds the answer (max value, count, or feasibility flag) considering exactly those i items at capacity c. The recurrence is:

dp_new[c] = combine(dp_old[c],          # skip item i
                    dp_old[c - w] ⊕ v)  # take item i

The whole question of forward vs reverse is: when I read dp[c - w] while computing dp[c], do I want it to be the old value (item not yet used → 0/1) or the new value (item already used → unbounded)? Reverse loop preserves old values to the right of c; forward loop overwrites left-to-right, so dp[c - w] is fresh by the time you read it.

That’s it. Every knapsack variant is a re-spelling of the same invariant with a different combine operator (max, +, or, min + 1).

Complexity

• Time: O(n · W) where n is the number of items and W the budget. For Ones-and-Zeroes it’s O(n · m · n) (two capacities). For unbounded knapsack, same O(n · W).
• Space: O(W) after collapsing the 2D table to a single row. The 2D form is O(n · W) and is what you write first when debugging — collapse only after the recurrence is verified.

Common pitfalls

• Looping capacity in the wrong direction. Forward loop on a 0/1 problem reuses items silently and inflates your answer. Reverse loop on an unbounded problem under-counts. Both bugs pass small tests and fail on the bigger ones — get the direction right by construction, not by experiment.
• Reducing to the wrong target. Partition problems target S / 2, not S. Target-sum reduces to subset-sum with target (S + T) / 2, which is invalid (not an integer) when S + T is odd or T > S — handle those edges before allocating dp.
• Forgetting the empty-subset base case. dp[0] = 1 (count) or dp[0] = True (feasibility) is what makes the recurrence bottom out. Skip it and every count is zero.
• Treating fractional knapsack as DP. Fractional knapsack is greedy: sort by value / weight descending and fill. Only the indivisible (0/1) version needs DP. Mixing them up wastes hours.
• Initialising for “min coins” wrong. Coin Change (LC 322) asks for minimum coins. Initialise dp = [inf] * (amount + 1) with dp[0] = 0, then dp[c] = min(dp[c], dp[c - coin] + 1). Using zeros as the sentinel collapses the recurrence.

Where you see this in production

• Cluster schedulers (Borg, Kubernetes, YARN). Pod packing onto nodes is a multi-dimensional bin-pack — capacities are CPU, memory, GPU, ephemeral disk; items are pods with resource requests. Production schedulers don’t solve it optimally (NP-hard), but the scoring functions and admission checks use the same dp-style “does this fit, what’s the best fit” reasoning, often with simulated knapsack subroutines for pre-emption decisions.
• AWS Spot Fleet / EC2 capacity optimizers. Picking which instance types to bid on under a target capacity and price ceiling is a knapsack: each instance type has a vCPU/memory “weight” and a spot-price “cost”, and you want to hit the requested capacity at minimum cost without exceeding the bid budget.
• Ad-budget pacing and bidding. Real-time bidders like Google Ads’ smart bidding decide which impressions to bid on within a daily budget — each impression is an item with predicted value (conversion probability × bid) and cost (winning price). The offline planner that allocates budget across campaigns runs a knapsack-style LP whose integer fallback is exactly 0/1 knapsack.
• Adaptive bitrate ladders (HLS, DASH, Netflix Per-Title encoding). When choosing which (resolution, bitrate) rungs to encode for a given title, encoders solve a constrained selection: maximise quality (VMAF) within a storage and CDN-egress budget. Netflix’s per-title encoding pipeline frames rung selection as a knapsack on the convex hull of quality-vs-bitrate points.

Practice problems

Resources

• NeetCode roadmap — neetcode.io/roadmap — pattern-by-pattern problem sets organised exactly like this site.
• NeetCode practice grid — neetcode.io/practice — track which problems you’ve solved per pattern.
• NeetCode YouTube — @NeetCode — clear, whiteboard-style walkthroughs for almost every LeetCode problem above.
• Striver / Take U Forward — DP playlist — www.youtube.com