DPAlgorithmaka capacity DP, subset-sum DP, bounded/unbounded knapsack

Knapsack DP

State is (items considered, capacity used); choose items to maximize value or count/decide subsets hitting a target sum.

▶ VisualizePattern: Dynamic ProgrammingPractice (3)
Progress

Overview

Knapsack DP covers every problem where you select items under a numeric budget: weights against a capacity, coins against an amount, numbers against a target sum. The state is dp[i][w] = best value (or number of ways, or feasibility) using the first i items with capacity w. The two variants differ in one loop direction: 0/1 (each item at most once, 0/1 Knapsack) iterates capacity downward when rolled to one row; unbounded (unlimited copies, Unbounded Knapsack, Coin Change) iterates upward so an item can be reused.

Complexity is O(n · W) time and O(W) space — pseudo-polynomial, because W is a value, not an input length. Typical constraints: n ≤ 100–1000, W ≤ 10^4–10^5, product ≤ ~10^8. If W is 10^9 the intended solution is not this DP.

Members: 0/1 knapsack, subset sum, partition equal subset sum, target sum (+/- assignment), coin change (min coins and number of ways), unbounded knapsack, bounded knapsack (each item up to c_i times — binary-split items into powers of two), and multi-dimensional knapsack (two capacities → dp[w1][w2]).

knapsacksubset sumcapacityO(nW)pseudo-polynomial1D rolling

Intuition

A mental model before the formal terms.

You have a shelf with slots labelled 0..W. Slot w records "the best I can do if my bag can hold exactly w". Go through items one by one; for each item, look at every slot and ask "would adding this item to a bag of capacity w - weight beat what I already have in slot w?".

Why the loop direction matters: if you scan slots from large to small, slot w - weight still holds the value before this item was considered, so the item is used at most once. If you scan from small to large, slot w - weight may already include this item, so you can stack copies — that is precisely unbounded knapsack.

How it works

  1. State: dp[i][w] — best value from items 0..i-1 with capacity w. For counting: number of ways; for feasibility: boolean.
  2. Transition (0/1): dp[i][w] = max(dp[i-1][w], dp[i-1][w - wt[i-1]] + val[i-1]) when wt[i-1] ≤ w. (Unbounded): replace the second term with dp[i][w - wt[i-1]] + val[i-1] (same row, item reusable).
  3. Base cases: dp[0][w] = 0 for max value; dp[0][0] = 1, dp[0][w>0] = 0 for counting; dp[0][0] = true for feasibility; dp[0][w>0] = INF for min-count.
  4. Order: items outer, capacity inner. Optimization: one row; inner loop w from W down to wt (0/1) or from wt up to W (unbounded).
  5. Counting subtlety: with items outer and capacity inner you count combinations (order of coins irrelevant). With capacity outer and items inner you count permutations (ordered sequences). Choose deliberately.

Why it works

For the last item there are only two futures — it is in the optimal bag or not. In either case the remaining choice is an optimal packing of the previous items into the remaining capacity, so enumerating both and taking the best is exact.

The rolled single row is correct because the downward scan guarantees every read of dp[w - wt] sees the previous item's row; the upward scan guarantees it sees the current item's row, which is the unbounded recurrence.

Recognition

How to tell a problem wants this.

  • Choose a subset of items subject to a total weight/cost limit, maximizing value or hitting an exact total.
  • "Can the array be partitioned into two equal-sum halves?", "how many ways to make amount A with these coins?", "fewest coins".
  • Constraint on the sum/capacity is moderate (≤ 10^5) while the items are few — the product hints at O(nW).
  • The word "unlimited" or "as many times as you like" → unbounded; "each once" → 0/1.
“number of ways” → Dynamic Programming

Interactive visualization

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

Showing the closely related 0/1 Knapsack visualization.

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

1# 0/1 knapsack, one row
2dp = [0] * (W + 1)
3for (wt, val) in items:
4  for w from W down to wt:            # downward: item used at most once
5    dp[w] = max(dp[w], dp[w - wt] + val)
6return dp[W]
7# unbounded: for w from wt up to W  (upward: item reusable)

Implementations

1# Representative problem: 0/1 knapsack (max value under capacity W), one-row table
2def knapsack01(weights: list[int], values: list[int], W: int) -> int:
31 · One-row table over capacities
4    dp = [0] * (W + 1)              # dp[w] = best value using items seen so far, capacity w
52 · Consider items one at a time
6    for wt, val in zip(weights, values):
73 · Capacity loop DOWNWARD so each item is used at most once
8        for w in range(W, wt - 1, -1):
94 · Transition: skip item i, or take it
10            dp[w] = max(dp[w], dp[w - wt] + val)
115 · Read the answer
12    return dp[W]
13 
14 
15if __name__ == "__main__":
16    print(knapsack01([1, 3, 4, 5], [1, 4, 5, 7], 7))  # 9 (items of weight 3 and 4)
Walkthrough
  1. Representative example of knapsack DP: one list over capacities; zip(weights, values) pairs each item's weight and value.
  2. range(W, wt - 1, -1) walks capacities downward, so dp[w - wt] still reflects the state *before* this item — each item is used at most once.
  3. The transition is max(skip, take) with no conditionals.
  4. dp[W] is the best achievable value (9 in the example).
Complexity (this implementation)
time O(n·W) · space O(W)

Pure Python manages roughly 10^6–10^7 inner-loop steps per second; large n·W wants PyPy, numpy tricks, or a rethink.

Language notes
  • zip over parallel lists is cleaner than index juggling and stops at the shorter list — validate lengths first if they might differ.
  • For subset-sum feasibility use a set of reachable sums or an int as a bitset (bits |= bits << wt) — Python's big ints make the bitset trick one line.
  • The upward-range version is unbounded knapsack; keep the direction visible in code review.
Common mistakes in this language
  • Writing range(W, wt, -1) and never updating dp[wt] itself.
  • Iterating capacities upward in the 0/1 variant.
  • Rebuilding dp inside the item loop, which silently resets progress.
Language differences that matter here
  • Loop direction carries the semantics in every language: downward = 0/1, upward = unbounded. The bug compiles and runs everywhere.
  • Bitset acceleration for subset-sum: C++ std::bitset, Python arbitrary-precision int shifts; JS/TS need a hand-rolled BigInt or typed-array bitset.
  • Value overflow: C++ picks int vs long long up front; JS/TS silently lose precision past 2^53; Python is exact.

Complexity

Best
—
Average
—
Worst
O(n · W)
Space
O(W) with a rolled row (O(n · W) if reconstruction is needed)

Pseudo-polynomial: W is a magnitude, not a length. Bounded knapsack with binary splitting is O(W · Σ log c_i).

Compare growth rates in the Complexity Explorer →

When to use — and when not to

Use it when
  • Selecting items under a numeric budget with moderate budget size.
  • Exact-sum feasibility or counting over a set of numbers (partition, target sum).
  • Coin systems that are not canonical, where greedy fails (coins {1, 3, 4}, amount 6).
Avoid it when
  • Capacity is huge (10^9+) — O(nW) is infeasible; consider meet-in-the-middle for n ≤ 40, or greedy if the problem is Fractional Knapsack.
  • Items are divisible — Fractional Knapsack is greedy by value density.
  • The coin system is canonical (1, 5, 10, 25) and only the minimum count is asked — greedy works, though DP is still safe.

Alternatives

Fractional KnapsackGreedy AlgorithmsSubsets (Power Set)Bitmask DP

Common mistakes

  • Iterating capacity upward in 0/1 knapsack — silently turns it into unbounded.
  • Counting permutations when combinations were asked (or vice versa) by swapping the loop nesting.
  • Initializing min-coins dp with 0 instead of INF, so every amount looks free.
  • Sizing the table W instead of W + 1.
  • Forgetting the "item does not fit" branch when wt > w (should just carry dp[i-1][w]).

Interview patterns

  • 0/1 Knapsack, Subset Sum, Partition Equal Subset Sum, Target Sum (transform to subset count).
  • Coin Change (min coins) and Coin Change II (number of combinations).
  • Last Stone Weight II (minimize difference = subset sum closest to half).
  • Ones and Zeroes (2D capacity), Profitable Schemes (capacity + count).
Interview questions on this
Mock interviews

Example problems

Combination SummediumCoin ChangemediumPartition Equal Subset Summedium