DPAlgorithmaka binary knapsack, bounded knapsack (one copy)

0/1 Knapsack

Choose a subset of items, each used at most once, maximizing total value without exceeding a weight capacity.

▶ VisualizePattern: Dynamic ProgrammingPractice (2)
Progress

Overview

Given n items with weights w[i] and values v[i] and a knapsack of capacity W, pick a subset with total weight ≤ W and maximum total value. Each item is either taken or left — hence "0/1". The problem is NP-hard in general, but when W is a moderate integer the DP over (items, capacity) runs in O(n·W), which is pseudo-polynomial.

It is the parent of a whole family — subset sum, partition equal subset sum, target sum, and the unbounded and bounded variants (see Knapsack DP). Learn this one thoroughly; the others are edits to the transition or the loop direction.

2D DPknapsacksubset selectionO(n·W)pseudo-polynomialrolling array

Intuition

A mental model before the formal terms.

Take three items: weights {1, 3, 4}, values {15, 20, 30}, capacity W = 4. Greedy by value/weight ratio takes item 1 (ratio 15), then item 2 (ratio 6.67) — total weight 4, value 35. But {item 3} alone gives weight 4, value 30, and {item 1, item 2} gives 35; the true optimum is 35 here, but change item 3 to value 40 and greedy still returns 35 while the optimum is 40. The point: whether to take an item depends on the *whole* remaining budget, not on a local ratio.

The DP asks one question per item: "with capacity c, is the best I can do with items 1..i better by skipping item i, or by taking it and asking the same question for items 1..i-1 with capacity c - w[i]?" Fill a table of answers to all those questions and the top-right cell is the result.

How it works

  1. State: dp[i][c] = maximum value using only the first i items with total weight ≤ c. Table size (n+1) × (W+1).
  2. Transition: dp[i][c] = dp[i-1][c] (skip item i); if w[i] ≤ c also consider dp[i-1][c - w[i]] + v[i] (take it) and keep the max. Both branches read row i-1 only.
  3. Base case: dp[0][c] = 0 for all c (no items, no value). If the question is "exactly weight c" instead of "at most", use -∞ for dp[0][c>0].
  4. Iteration order: i from 1 to n (outer), c from 0 to W (inner, any direction in the 2D version).
  5. Answer location: dp[n][W]. To reconstruct the chosen items, walk back from (n, W): if dp[i][c] != dp[i-1][c] item i was taken and c -= w[i].
  6. Space optimization: row i depends only on row i-1, so keep one array dp[c] and iterate c from `W` down to `w[i]`. The descending order guarantees dp[c - w[i]] still holds the previous row's value (item i not yet used) when dp[c] reads it. Ascending order would allow item i to be counted twice — that is exactly Unbounded Knapsack.

Why it works

Optimal substructure: consider any optimal solution for items 1..i and capacity c. Either it excludes item i, in which case it is an optimal solution for (i-1, c) — if a better one existed we could swap it in. Or it includes item i, in which case the rest is an optimal solution for (i-1, c - w[i]) by the same exchange argument. The transition considers both cases, so it computes the true optimum.

Overlapping subproblems: the recursive tree has 2^n leaves but only (n+1)(W+1) distinct (i, c) pairs. Tabulation touches each once with O(1) work.

The 1D reverse-loop trick is correct because writing dp[c] for large c first never disturbs dp[c'] for c' < c, which are the only cells later iterations read.

Recognition

How to tell a problem wants this.

  • "Choose a subset" + "each item at most once" + "capacity / budget / limit" + "maximize value" or "is a total achievable".
  • Constraints like n ≤ 100, W ≤ 10^4 or sum(nums) ≤ 2·10^4 — small enough for n·W but far too large for 2^n.
  • Subset sum, partition into two equal halves, target sum with ± signs — all disguised 0/1 knapsacks with a boolean or counting table.
“number of ways” → Dynamic Programming

Interactive visualization

Play, step, change the input. ← → and space work too.

01234567
∅00000000
w1 v1········
w3 v4········
w4 v5········
w5 v7········
1/39Row 0 means "no items considered": the best value is 0 for every capacity.
Cell being filledDependency readBase caseComputedReconstructed choice
PseudocodeLearn 0/1 Knapsack →
1dp[0][*] = 0
2for i in 1 .. n:
3  for c in 0 .. W:
4    dp[i][c] = dp[i-1][c]            // skip item i
5    if w[i] <= c:
6      dp[i][c] = max(dp[i][c], dp[i-1][c-w[i]] + v[i])  // take
7traceback from dp[n][W]
Variables
n4
W7
Complexity
best O(n·W)
avg O(n·W)
worst O(n·W)
space O(W)
Speed

Pseudocode

1dp = array[W + 1] filled with 0
2for i in 0..n-1:
3  for c from W down to w[i]:
4    dp[c] = max(dp[c], dp[c - w[i]] + v[i])
5return dp[W]

Implementations

1# dp[i][c] = best value using the first i items with capacity c
2def knapsack_01(weights: list[int], values: list[int], W: int) -> int:
31 · State table
4    n = len(weights)
5    dp = [[0] * (W + 1) for _ in range(n + 1)]
62 · Base cases
7    # row 0 (no items) is all zeros — already set by the comprehension
83 · Transition
9    for i in range(1, n + 1):
10        w, v = weights[i - 1], values[i - 1]
11        for c in range(W + 1):
12            dp[i][c] = dp[i - 1][c]                                  # skip item i
13            if w <= c:
14                dp[i][c] = max(dp[i][c], dp[i - 1][c - w] + v)       # take it
154 · Answer
16    return dp[n][W]
17 
18 
195 · Reconstruction
20def knapsack_01_items(weights: list[int], values: list[int], W: int) -> list[int]:
21    n = len(weights)
22    dp = [[0] * (W + 1) for _ in range(n + 1)]
23    for i in range(1, n + 1):
24        w, v = weights[i - 1], values[i - 1]
25        for c in range(W + 1):
26            dp[i][c] = dp[i - 1][c]
27            if w <= c:
28                dp[i][c] = max(dp[i][c], dp[i - 1][c - w] + v)
29    chosen: list[int] = []
30    c = W
31    for i in range(n, 0, -1):
32        if dp[i][c] != dp[i - 1][c]:  # value changed => item i was taken
33            chosen.append(i - 1)
34            c -= weights[i - 1]
35    return chosen[::-1]
Walkthrough
  1. [[0] * (W + 1) for _ in range(n + 1)] creates a fresh inner list per row — [[0] * (W + 1)] * (n + 1) would alias one row n+1 times.
  2. Row 0 is all zeros, the base case.
  3. w, v = weights[i - 1], values[i - 1] converts 1-based table row to 0-based item index once per row.
  4. The transition first copies the skip value, then applies max with the take branch.
  5. Reconstruction walks rows backward; chosen[::-1] restores ascending order.
Complexity (this implementation)
time O(n·W) · space O(n·W)

Python lists of ints are pointer arrays; for W in the 10^5 range the 2D table can be hundreds of MB — use the 1D form or array("i").

Language notes
  • 1D rolling form: for c in range(W, w - 1, -1): dp[c] = max(dp[c], dp[c - w] + v) — the w - 1 stop is inclusive of w.
  • zip(weights, values) iterates item pairs without index bookkeeping.
  • lru_cache on a nested function keyed by (i, cap) is the top-down form; recursion depth is n, which is fine for n ≤ ~900.
Common mistakes in this language
  • Aliased rows from [[0] * (W + 1)] * (n + 1) — updates to dp[1] show up in every row.
  • Writing range(W, w, -1) and never processing capacity exactly w.
  • Confusing the 1-based table index i with the 0-based item index i - 1.
Language differences that matter here
  • 2D table construction: C++ nested std::vector constructor copies the inner vector per row (safe); JS/TS fill(row) and Python [row] * n both alias a single row — use Array.from with a factory / a list comprehension.
  • Overflow: C++ int wraps when the summed values exceed 2^31 (use long long); JS/TS stay exact below 2^53; Python is exact.
  • Memo key for (i, cap): C++ 2D vector, JS/TS numeric composite key in a Map, Python tuple via lru_cache.
  • Descending range: C++ for (c = W; c >= w; c--), JS/TS the same, Python range(W, w - 1, -1) (stop is exclusive).

Complexity

Best
O(n·W)
Average
O(n·W)
Worst
O(n·W)
Space
O(W)

Pseudo-polynomial: depends on the numeric value of W, not its bit length. 2D table (needed for reconstruction) uses O(n·W) space.

Compare growth rates in the Complexity Explorer →

When to use — and when not to

Use it when
  • Subset selection under one additive constraint with each item usable at most once, where the capacity is a moderate integer.
  • Feasibility variants (subset sum, partition) with a boolean table: dp[c] |= dp[c - w].
  • Counting variants ("how many subsets sum to target"): dp[c] += dp[c - w], same downward loop.
Avoid it when
  • Capacity is huge (10^9) or fractional — the table does not fit; use meet-in-the-middle for small n, branch and bound, or approximation.
  • Items are divisible — Fractional Knapsack is greedy and optimal in O(n log n).
  • Items can be reused without limit — that is Unbounded Knapsack, which uses the ascending loop.

Alternatives

Unbounded KnapsackFractional KnapsackSubsets (Power Set)Bitmask DP

Common mistakes

  • Iterating capacity upward in the 1D version — silently turns the problem into unbounded knapsack.
  • Confusing "at most W" with "exactly W" and initializing the base row with 0 in both cases.
  • Reconstructing the chosen items from the 1D array — it has no history; keep the 2D table or store parent pointers.
  • Sizing the table with W instead of W + 1, dropping capacity W itself.

Interview patterns

  • Partition Equal Subset Sum: boolean subset sum to total / 2.
  • Target Sum: count subsets with sum (total + target) / 2.
  • Last Stone Weight II: minimize total - 2·S over achievable subset sums S ≤ total / 2.
  • Ones and Zeroes: 0/1 knapsack with two capacities (2D rolling table, both loops downward).
Interview questions on this
Mock interviews

Example problems

Partition Equal Subset SummediumFractional Knapsackeasy