DP V — 0/1 Knapsack

A budget limits which combinations fit, and each item may be chosen only once. Derive the take-or-skip recurrence, compress its table without accidentally reusing an item, then adapt the state to reachability, counting and reconstruction.

Input contracts. Capacity optimization below assumes equally sized weight/value lists, positive integer weights and a nonnegative integer capacity. The empty subset is allowed. Subset-sum examples assume nonnegative integers; counting treats equal-valued positions as distinct items. Signed values require a different reachable-sum range, not adding a constant to every item.

Series: LeetCode — From Basics to Production-Ready · Session 37 / 65 · Phase 2 · Dynamic programming

Prerequisites

L33–L35 (state definition, recurrence, memo→table). You should be able to write take/skip 1D DP without notes. 0/1 knapsack is take/skip with a second axis — the remaining budget — so if L35 is shaky, do it first.

Why this session exists

Several problems share a take-or-skip state: "items with weights and values, a capacity W, maximise value, each item at most once." Related questions include: can this array be split into two equal-sum halves? (Partition Equal Subset Sum), how many ways to reach target T with +/- signs? (Target Sum), smallest difference between two piles? (Last Stone Weight II). Partition becomes a reachability problem, Target Sum becomes counting, and Last Stone Weight II minimizes a partition difference by finding a reachable sum closest to half the total.

The reason it is worth a whole session is the at-most-once constraint, which forces one specific detail in the space-optimised version: you iterate the capacity axis backwards. For the positive-weight recurrence used here, an ascending in-place pass permits repeated use of the current item. It therefore solves the unbounded variant (L38) and can return a wrong answer for a 0/1 input.

The literal backpack

Real: You are a thief with a backpack that holds W kilograms. Each item has a weight and a value. You can take an item or leave it — you cannot take half an item, and you cannot take the same item twice (there's one of each). Maximise the value you carry out. The nonnegative subset-sum examples below use the same two-way choice; other subset constraints may require additional state.

# items = [(weight, value), ...], capacity W
# choose a subset with total weight <= W maximising total value
# each item used 0 or 1 times  -> '0/1'

Blank-file warm-up

Five minutes, empty file, no notes. Write the 1D roll from memory:

for each item (w, v):
    for cap from W down to w:          # BACKWARDS — this is the whole game
        dp[cap] = max(dp[cap], dp[cap - w] + v)

If the loop direction wobbles, you do not know this session yet. Backwards = each item used at most once. Forwards = unbounded (L38).

From first principles

Question: Why does 0/1 knapsack need a capacity axis, and why does the 1D version iterate capacity backwards?

Premise: Define dp[i][c] = the best value achievable using items 0..i-1 with total weight at most c.

Because: One index is not enough: 'I've considered i items' doesn't fix what I can still afford — the remaining budget c is a second, independent piece of state.

Premise: For item i-1 with weight w and value v: either skip it (dp[i-1][c]) or take it (dp[i-1][c-w] + v, only if w <= c). Take the max.

Because: Every subset either contains item i-1 or it doesn't; both branches reduce to a strictly smaller subproblem on items 0..i-2.

Premise: The 2D table only ever reads the PREVIOUS row (i-1), so we can collapse to a single array dp[c] rolled over items.

Because: Two arrays always separate these rows. A single array is also sufficient for this positive-weight recurrence when the update order preserves each dependency from the previous row; dependence only on the previous row does not, by itself, prove arbitrary in-place updates safe.

Premise: When rolling, we must iterate c from high to low. If we went low to high, dp[c-w] would already reflect item i (this iteration), letting us take item i twice.

Because: Backwards iteration guarantees dp[c-w] still holds the PREVIOUS row's value — item i unused there — enforcing 'at most once'.

Conclusion: 0/1 knapsack = take/skip with a budget axis. The at-most-once rule lives entirely in the backwards capacity loop of the 1D version.

The 2D table, easiest to reason about:

def knapsack_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-1
            if w <= c:
                dp[i][c] = max(dp[i][c], dp[i - 1][c - w] + v)   # take it
    return dp[n][W]
 
assert knapsack_2d([1, 3, 4, 5], [1, 4, 5, 7], 7) == 9   # items (3,4)+(4,5) -> weight 7, value 9

The space-optimized 1D version, when only the optimal value is required:

def knapsack_1d(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):        # HIGH -> LOW: at most once
            dp[c] = max(dp[c], dp[c - w] + v)
    return dp[W]
 
assert knapsack_1d([1, 3, 4, 5], [1, 4, 5, 7], 7) == 9

Change that inner loop to range(w, W + 1) (forwards) and you get unbounded knapsack — each item reusable. It can overestimate the 0/1 optimum; on some inputs the two variants happen to agree. Use the one-item counterexample below rather than assuming every test will expose the mistake.

Mental model

Name: Two axes: item index and budget

Picture: A grid. Rows are items (add one at a time). Columns are the remaining capacity 0..W. Each cell asks the same question: with these items and this budget, what's my best value? You fill it by looking straight up (skip) or up-and-left-by-w (take). The 1D roll flattens the rows away, and the only trace of 'at most once' left behind is that you sweep the budget right-to-left.

• Two pieces of state ⇒ two loops: outer over items, inner over capacity.

• 0/1 (one of each) ⇒ inner capacity loop goes HIGH → LOW.

• Boolean variant (reachable?): dp[c] = dp[c] or dp[c-w].

• Counting variant (how many ways?): dp[c] += dp[c-w].

Trigger: A fixed set of items, each usable at most once, with a numeric budget/target to hit or maximise under.

Memory hook

"One of each, sweep the budget backwards." The phrase binds the constraint (one of each item) to the fix (backwards capacity loop). Its sibling in L38 is "unlimited, sweep forwards." Use the pair as a reminder, then justify it by checking which item-row each dependency represents.

Myth: 0/1 and unbounded knapsack differ only in the problem statement; the code is basically the same.

Truth: With the same positive-weight maximum-value recurrence, changing range(W, w - 1, -1) to range(w, W + 1) changes the update order from descending to ascending. That is a loop-bound and step change, not literally a one-character edit.

Why: On weights=[2], W=4, target 'max count of item': backwards gives dp[4]=value-of-one-item; forwards gives dp[4]=value-of-two-items. Same code shape, different loop direction, different problem.

Test: After writing the 1D loop, ask: 'can dp[c-w] on THIS iteration already include the current item?' If yes (forward), it's unbounded. If no (backward), it's 0/1.

Related problem families

These practice problems illustrate different state meanings and constraints. They are a study selection, not a claim about interview frequencies.

• LC416 · Partition Equal Subset Sum — Practice selection. Reduce to: is there a subset summing to total/2? Boolean 0/1 knapsack with capacity = sum/2. Probe: do you spot that odd total ⇒ instant False, and that this is subset-sum, not a fresh DP? Follow-up: what if you needed the actual subset?
• LC494 · Target Sum — Practice selection. Assign +/- to each number to hit target T. Algebra: elements assigned + form a subset summing to (T + total)/2, so it's counting 0/1 knapsack (dp[c] += dp[c-w]). Probe: the reduction, and the parity/bounds check that makes (T+total) even and non-negative.
• LC1049 · Last Stone Weight II — Practice selection. Minimise the final stone = split into two piles with minimal difference = find the subset summing closest to total/2. Probe: recognising "minimal difference of two piles" as subset-sum.
• LC474 · Ones and Zeroes — Practice selection. A two-budget 0/1 knapsack (m zeros and n ones as twin capacities). Probe: can you carry TWO capacity axes and still keep both loops backwards?
• LC698 · Partition to K Equal Sum Subsets — Practice selection. Generalisation; usually needs bitmask/backtracking, but candidates who know subset-sum reason about it faster. Probe: why the simple knapsack doesn't directly extend to k parts.
• LC322 · Coin Change — Practice selection. This is the UNBOUNDED cousin (L38) — included here so you feel the contrast: same table shape, forward loop, coins reusable.

A useful study order is maximum value → boolean subset-sum → counting subset-sum → two budgets → k-partition. The last step needs additional machinery; it is not a claim that interviewers follow a fixed sequence.

A worked reduction: Partition Equal Subset Sum

Brute force: try all 2ⁿ subsets, check if any sums to total/2 — exponential. The insight: this is exactly "can I fill a backpack of capacity total/2 exactly?", a boolean 0/1 knapsack.

def can_partition(nums: list[int]) -> bool:
    total = sum(nums)
    if total % 2:                        # odd total can't split evenly
        return False
    target = total // 2
    dp = [False] * (target + 1)
    dp[0] = True                         # sum 0 is always reachable (empty subset)
    for x in nums:
        for c in range(target, x - 1, -1):   # backwards: each number once
            dp[c] = dp[c] or dp[c - x]
    return dp[target]
 
assert can_partition([1, 5, 11, 5]) is True     # [1,5,5] and [11]
assert can_partition([1, 2, 3, 5]) is False

• Complexity: O(n · target) time, O(target) space.
• Follow-up they escalate to: return the actual subset (keep parent pointers), or handle very large sums (then the pseudo-polynomial DP is too big and you discuss why no truly polynomial solution is known — subset-sum is NP-complete).

A second worked reduction: Target Sum

Plain words. Given nums and a target T, put a + or a - in front of every number so the expression evaluates to T. Count how many sign assignments work.

Brute force. Two choices per element give 2^n assignments: about one million at n = 20 and one trillion at n = 40. Feasibility depends on the work per assignment and available resources; the growth, not a universal time threshold, motivates the DP.

The insight. Split the numbers into the set P you sign positive and the set N you sign negative. Then sum(P) - sum(N) = T and sum(P) + sum(N) = total. Add them: 2 * sum(P) = T + total, so sum(P) = (T + total) / 2. The question collapses to: how many subsets sum to that value? That is counting 0/1 knapsack, and the recurrence changes from or to +=.

def findTargetSumWays(nums: list[int], target: int) -> int:
    total = sum(nums)
    need = target + total
    # (T + total) must be even and non-negative, else no assignment exists
    if need % 2 or need < 0:
        return 0
    s = need // 2
    if s > total:                        # target unreachable even signing everything +
        return 0
    dp = [0] * (s + 1)
    dp[0] = 1                            # exactly one way to make 0: choose nothing
    for x in nums:
        for c in range(s, x - 1, -1):    # backwards — each number used at most once
            dp[c] += dp[c - x]           # counting, not boolean
    return dp[s]
 
assert findTargetSumWays([1, 1, 1, 1, 1], 3) == 5
assert findTargetSumWays([1], 2) == 0

O(n · s) time, O(s) space. Note the zero-handling subtlety: a 0 in nums can be signed either way and doubles the count, and this formulation handles it correctly for free because dp[c] += dp[c - 0] doubles every cell.

The follow-up they escalate to: "what if the numbers can be negative?" The algebra assumed non-negative values so that sum(P) is a valid capacity. With negatives, offset the indices of the reachable sum range (not the item values), or use a dictionary-keyed DP over signed reachable sums.

Goal: Turn the boolean subset-sum into a reconstruction.

Hint: Keep a 2D table instead of the rolled 1D array, then walk backwards from dp[n][target]: if dp[i-1][c] is True the item was skipped, otherwise it was taken and you move to c - w[i].

def partition_subset(nums):
    total = sum(nums)
    if total % 2:
        return None
    t = total // 2
    n = len(nums)
    dp = [[False] * (t + 1) for _ in range(n + 1)]
    for i in range(n + 1):
        dp[i][0] = True
    for i, x in enumerate(nums, 1):
        for c in range(t + 1):
            dp[i][c] = dp[i - 1][c] or (x <= c and dp[i - 1][c - x])
    if not dp[n][t]:
        return None
    chosen = []
    c = t
    for i in range(n, 0, -1):
        if not dp[i - 1][c]:
            chosen.append(i - 1)  # return indices: equal values remain distinct items
            c -= nums[i - 1]
    return chosen

Tradeoff

Decision: 2D table vs 1D rolled array for knapsack under a tight review.

Name: 2D table dp[i][c]

Gain: Easiest to reason about and to reconstruct the chosen items by walking backwards through rows. Hard to introduce the loop-direction bug.

Cost: O(n·W) space, which can be large; slower to write.

Pick: when a reviewer also wants WHICH items were chosen, or when you want to explain the recurrence cleanly first.

Name: 1D rolled dp[c]

Gain: O(W) auxiliary cells and a concise value-only computation.

Cost: The backwards capacity loop is a silent-bug magnet; reconstruction of the item set is awkward.

Pick: as the final optimisation once you've established the 2D recurrence — and only after saying the loop direction out loud.

Verdict: Derive the 2D recurrence, then roll to 1D and explicitly narrate 'backwards because each item is used at most once'. That dependency argument explains why the optimization preserves the recurrence.

In practice

A simplified budget-allocation model fits this recurrence when jobs have independent integer costs and additive benefits and each job is chosen at most once. Real schedulers may also have dependencies, deadlines, multiple resources or changing benefits, so the plain knapsack model is not automatically sufficient. Because table size grows with the numeric capacity, inspect that capacity before choosing this method.

You are ready to move on when you can

• Write the 1D knapsack from memory with the capacity loop backwards, and say WHY backwards.

• Reduce Partition Equal Subset Sum to boolean subset-sum, including the odd-total shortcut.

• Reduce Target Sum to counting subset-sum via the +/- algebra.

• State how descending versus ascending in-place capacity updates change item reuse.

• Explain why knapsack is 'pseudo-polynomial' and what that means for large sums.

Self-check (answer follows each question).

Check yourself

Q: In the 1D 0/1 knapsack, why must the capacity loop go from high to low?

A: So dp[c-w] still holds the previous item-row's value (item not yet used this pass), enforcing 'each item at most once'. Forward iteration would let dp[c-w] already include the current item, making it reusable (unbounded).

Q: How does Partition Equal Subset Sum become knapsack?

A: If total is even, ask whether some subset sums to total/2. That's a boolean 0/1 knapsack with capacity total/2; dp[c] = dp[c] or dp[c-x].

Q: In Target Sum, what subset-sum are you actually counting?

A: Let P = subset assigned '+'. Then sum(P) - (total - sum(P)) = T, so sum(P) = (T + total)/2. Count subsets summing to that value with dp[c] += dp[c-x].

Q: What single change turns 0/1 knapsack into unbounded knapsack?

A: Reverse the inner capacity loop to iterate low → high (range(w, W+1)), so each item can be reused.

Q: Why is knapsack called 'pseudo-polynomial'?

A: Its runtime O(n·W) is polynomial in n and in the numeric VALUE W, but exponential in the number of bits used to write W. For huge W it blows up; subset-sum is NP-complete.

Stretch: An array of 10^12 cells is impractical in ordinary memory even before processing items. For small n, meet-in-the-middle can instead enumerate two halves in roughly O(2^(n/2)) space/time before sorting and combining; approximation or problem-specific structure may offer other tradeoffs. There is no capacity threshold that guarantees instant execution independently of n and the runtime.

Practice queue

Solve in this order; log each as cold / warm / hint / failed.

1. LC416 Partition Equal Subset Sum — boolean subset-sum, the gateway.
2. LC494 Target Sum — counting subset-sum.
3. LC1049 Last Stone Weight II — minimal-difference subset-sum.
4. LC474 Ones and Zeroes — two-budget knapsack.
5. LC698 Partition to K Equal Sum Subsets — where knapsack meets bitmask/backtracking.
6. LC2915 Longest Subsequence That Sums to Target — maximising subset-sum, so the cell holds a length rather than a boolean.
7. LC1751 Maximum Number of Events That Can Be Attended II — knapsack where the "capacity" is a count of picks and the skip-branch needs a binary search.

Spaced-repeat anchors: LC416 and LC494. Those two carry the boolean and the counting recurrences respectively; re-solve both at +7d and again at +21d. Everything else in this session is a variation on one of them.

• 0/1 knapsack = take/skip with a budget axis; items used at most once.

• In the 1D roll, sweep capacity HIGH → LOW — that single direction encodes 'at most once'.

• Related state meanings include subset-sum reachability, Target Sum counting, and a minimum partition difference.

• It's pseudo-polynomial: fast only when the budget/sum is small; subset-sum is NP-complete.

Execution and complexity boundaries

The five displayed Python programs use valid inputs under the stated contracts; they are not input-validation APIs. Local tests compare the recurrences and reconstruction with bounded exhaustive subset/sign enumeration. Those tests do not establish speed for maximum constraints. Complexity counts table updates: Python integer counts can grow with n, so integer-arithmetic bit costs are additional to the stated O(n·s) operation count.

Corrective source notes

• Knapsack Problem - Algorithms for Competitive Programming — Zero-one knapsack row compression scans capacity downward so the dependency still refers to the previous item row. Checked 2026-10-07.
• Introduction to Dynamic Programming - Algorithms for Competitive Programming — Memoization stores subproblem results so repeated states need not be recomputed. Checked 2026-10-07.

These citations support the named claims, not blanket certification of the lesson. Worked proofs are derived in the text; execution scope and finite-test limits are recorded separately.