Knapsack DP

Pick items under a capacity, a target sum or a budget with one table indexed by capacity. The 0/1 and unbounded variants differ by one loop direction, and most subset-sum, coin and partition problems are knapsacks in disguise.

Overview

The problem

You have items, each with a weight and a value, and a bag that holds at most a fixed total weight, the capacity. Which items give the largest total value without going over? In the 0/1 knapsack each item is taken once or not at all. In the unbounded knapsack you may take any number of copies of an item.

The rest of this topic traces one small instance.

A — 2 — 3
B — 3 — 4
C — 1 — 2

The capacity is 5. The choices that fit are A + B (weight 5, value 7), B + C (weight 4, value 6) and A + C (weight 3, value 5). All three together weigh 6 and do not fit. The best value is 7.

Trying every subset works for three items, but there are 2ⁿ subsets: for 40 items that is about 1.1 trillion. Dynamic programming replaces the subsets with a table that has one cell per (item, capacity) pair.

The 2D table

Let dp[i][c] be the best value using only the first i items with capacity c. Row 0 is no items, so it is all zeros. Each other cell is the better of two moves.

Skip item i: dp[i][c] = dp[i−1][c].
Take item i, if its weight fits: dp[i][c] = dp[i−1][c − weight] + value.

Here is the full table for the example. The bold cells are where taking the item won.

none — 0 — 0 — 0 — 0 — 0 — 0
A (2, 3) — 0 — 0 — 3 — 3 — 3 — 3
A, B (3, 4) — 0 — 0 — 3 — 4 — 4 — 7
A, B, C (1, 2) — 0 — 2 — 3 — 5 — 6 — 7

Read one cell: dp[B][5] compares skipping B (dp[A][5] = 3) with taking B (dp[A][5 − 3] + 4 = 3 + 4 = 7), and keeps 7. The answer is the bottom-right cell, 7.

To find which items were taken, walk back from that cell. If dp[i][c] differs from dp[i−1][c], item i was taken; subtract its weight from c and move up a row. Here dp[C][5] equals dp[B][5], so C was skipped; dp[B][5] differs from dp[A][5], so B was taken and c becomes 2; dp[A][2] differs from dp[none][2], so A was taken. The items are A and B.

The table has (n + 1) × (capacity + 1) cells and each takes O(1), so the time is O(n × capacity).

One row and the loop direction

Each row reads only the row above it, so one row is enough. Loop over the items, and for each item update dp[c] = max(dp[c], dp[c − weight] + value). The direction of the capacity loop decides which problem you solve.

Downward (capacity to weight): dp[c − weight] has not been updated for this item yet, so it still holds the previous row. Each item is used at most once. This is 0/1.
Upward (weight to capacity): dp[c − weight] may already include this item, so the item can be used again. This is unbounded.

The one-row trace for 0/1, one row per item, matches the 2D table.

start — 0 — 0 — 0 — 0 — 0 — 0
A (2, 3), downward — 0 — 0 — 3 — 3 — 3 — 3
B (3, 4), downward — 0 — 0 — 3 — 4 — 4 — 7
C (1, 2), downward — 0 — 2 — 3 — 5 — 6 — 7

The same items with the upward loop give the unbounded answer.

start — 0 — 0 — 0 — 0 — 0 — 0
A (2, 3), upward — 0 — 0 — 3 — 3 — 6 — 6
B (3, 4), upward — 0 — 0 — 3 — 4 — 6 — 7
C (1, 2), upward — 0 — 2 — 4 — 6 — 8 — 10

The unbounded answer is 10: five copies of C. Look at dp[4] after A in the upward table. It reads dp[2], which already holds one A, and becomes 6, two copies of A. In the downward table dp[4] was filled before dp[2], so it read the old 0 and stayed at 3.

The four flavors

The same table answers four different questions. Only what a cell holds, its starting value and how two moves combine change.

the largest value within a capacity — the best value — 0 — max — 0/1 Knapsack
whether a sum can be made — true or false — true — or — Partition Equal Subset Sum
how many ways — a count — 1 — plus — Target Sum, Coin Change II
the fewest items to reach a target — a count, infinity when impossible — 0 — min — Coin Change, Perfect Squares

Problems in disguise

Problems rarely mention a bag. The items and the capacity hide in the story.

Partition Equal Subset Sum — the numbers — half the total; an odd total is an immediate no — 0/1 — can this sum be made
Target Sum — the numbers — P = (total + target) / 2, the sum of the numbers given a plus sign — 0/1 — how many subsets make P
Last Stone Weight II — the stones — half the total — 0/1 — can this sum be made
Coin Change — the coins — the amount — unbounded — fewest coins
Coin Change II — the coins — the amount — unbounded — how many combinations
Perfect Squares — 1, 4, 9, 16, … up to n — n — unbounded — fewest squares

Two of these need a short piece of algebra. In Target Sum, the numbers with a plus sign add to P and the ones with a minus sign add to N, so P − N = target and P + N = total. Adding the two equations gives P = (total + target) / 2. If that is not a whole number, or is negative, there are no ways. In Last Stone Weight II, smashing stones ends up splitting them into two piles whose difference is the answer, so find the largest reachable pile sum S that is at most half the total; the answer is total − 2S.

Here is the subset-sum trace for Partition Equal Subset Sum on [1, 5, 11, 5]. The total is 22, so the target is 11, and the row lists the sums that can be made.

start — 0
1 — 0, 1
5 — 0, 1, 5, 6
11 — 0, 1, 5, 6, 11
5 — 0, 1, 5, 6, 10, 11

11 is reachable, so the answer is yes: [1, 5, 5] against [11].

Counting: combinations or permutations

When a cell holds a count, the loop order decides what you count. With coins [1, 2] and amount 3, the combinations are {1, 1, 1} and {1, 2}: two. The permutations also count 2 + 1 separately from 1 + 2: three.

coins outside, amount inside — combinations: each coin is decided once, so order does not matter — after coin 1: 1, 1, 1, 1; after coin 2: 1, 1, 2, 2 — 2
amount outside, coins inside — permutations: every coin can be the last one added at every amount — after amount 1: 1, 1, 0, 0; after 2: 1, 1, 2, 0; after 3: 1, 1, 2, 3 — 3

Coin Change II wants combinations, so coins go outside. Combination Sum IV wants ordered sequences, so the amount goes outside.

When the table is too big

The time is O(n × capacity), and the capacity is a number in the input, not the size of the input. 100 items with capacity 10,000 is a million cells; 100 items with capacity a billion is 100 billion cells. This is called a pseudo-polynomial running time, and it means knapsack DP is only fast when the capacity is modest.

Few items (about 20 or fewer), huge capacity — try all 2ⁿ subsets, or split the items in two halves and combine (meet in the middle)
Huge weights but small values — index the table by value: dp[v] is the smallest weight that reaches value v
Large amounts (in the millions) in a yes/no subset sum — in Python, hold the reachable sums as the bits of one integer; for each number x, OR the integer with itself shifted left by x. A shift handles 64 sums per machine word, so this is a constant-factor gain, not a smaller table

What you will be able to do

Recognize a knapsack from a story about a budget, a target sum or a partition, and name the items and the capacity.
Fill a 2D table and a one-row table by hand, and recover which items were taken.
Choose the loop direction for 0/1 or unbounded, and explain why it works.
Pick the cell type, dp[0] and the combine step for value, yes/no, count and minimum questions.
Choose the loop order that counts combinations or permutations.

When to use it

Choosing items under a weight, cost or size limit to get the largest total value
Deciding whether some numbers add up to a target, or whether a set splits into two equal halves
Counting the ways to make a target from given values, with or without reuse
Finding the fewest coins, squares or pieces that reach a target
Assigning plus and minus signs to reach a target, which is a subset sum after a little algebra
Any problem where each item is taken or skipped and a running total must stay within a limit

More Coding & DSA topics

Start free on Cariara · Coding problems · System design studio