Medium Problemsknapsackoptimization

0-1 Knapsack Problem

Given n items, each with a weight and a value, and a knapsack with a fixed weight capacity, choose a subset of items, taking each item whole or not at all, to maximize total value without exceeding the capacity.

Do this lesson first: coin change

Example input

items as (weight, value) = (1, 1), (3, 4), (4, 5), (5, 7); capacity = 7

Expected output

9

Break it down

Answer each question out loud before you open it. Getting it wrong here is the useful part. A revealed answer you never guessed at teaches you nothing.

dp[i][c] is the best total value you can carry using only the first i items, each at most once, in a knapsack of capacity c. Two numbers name the state, so the table is a grid: row 0 for no items, then one row per item, and one column per capacity from 0 up to the knapsack's. A cell holds a value, not the list of items behind it; recovering the list is what printing-items-in-zero-one-knapsack is about.

dp[i][c] = max(dp[i - 1][c], v_i + dp[i - 1][c - w_i]), the second only when w_i <= c

Ask about the last item allowed, item i, which weighs w_i and is worth v_i. The best load from the first i items either leaves it out or puts it in. Out: the best load is the best from the first i - 1 items in the same capacity, the cell above. In: it is worth v_i and uses w_i of the capacity, and whatever else is in the knapsack must be the best load of the first i - 1 items in the c - w_i that remains, which is the cell w_i columns to the left in the row above. It is the row above because item i is already in and cannot go in twice. Take the larger. When w_i is more than c, the item cannot go in at all and the cell copies the one above.

Row 0 is the only base row: with no items allowed the knapsack stays empty, so every cell in row 0 is 0. Column 0 computes, and is 0 all the way down, because every item here weighs at least 1. Fill row by row; both cells a cell reads are in the row above, so they are final before anything reads them. In drive mode only the two-option cells in rows 2 to 4 are gated, because row 1's without-it option is always the empty knapsack's 0, so its comparison is a formality.

Tabulation over (n + 1) × (capacity + 1) cells. That cost grows with the capacity's VALUE, not with how many digits it has, which is why knapsack is called pseudo-polynomial: a capacity in the billions needs a different method. Every cell reads only the row above, so one row of capacity + 1 values is enough, as long as each pass sweeps c from HIGH to low. Sweeping upward lets item i read a cell already updated for item i on this pass, so item i can be counted again, and the loop silently solves unbounded-knapsack instead.

Time O(n × capacity)Space O(n × capacity), reducible to O(capacity) with one row swept from high to low

Fill the table

The table pauses before each cell you have to supply. Type the value the recurrence gives, and the write animation confirms it.

Step not started

Press start. The animation stops at every cell YOUR recurrence must fill.

Row 0 is the only base row: with no items allowed the knapsack stays empty, so every cell in row 0 is 0. Column 0 computes, and is 0 all the way down, because every item here weighs at least 1. Fill row by row; both cells a cell reads are in the row above, so they are final before anything reads them. In drive mode only the two-option cells in rows 2 to 4 are gated, because row 1's without-it option is always the empty knapsack's 0, so its comparison is a formality.

Rows ↓
Cols →

0

1

2

3

4

5

6

7

none

0

w1 v1

0

1

w3 v4

0

1

4

5

w4 v5

0

1

4

5

6

9

w5 v7

0

1

4

5

7

8

9

Rows ↓row i: may use the first i items

Cols →capacity c: best value that fits

zero-one-knapsack.ts

1function knapsack(weights, values, capacity) {
2 const n = weights.length;
3 const dp = Array.from({ length: n + 1 }, () => new Array(capacity + 1).fill(0));
4 // row 0: no items, so value 0 at every capacity
5 for (let i = 1; i <= n; i++) {
6 const w = weights[i - 1], v = values[i - 1];
7 for (let c = 0; c <= capacity; c++) {
8 dp[i][c] = dp[i - 1][c];
9 if (w <= c) dp[i][c] = Math.max(dp[i][c], v + dp[i - 1][c - w]);
10 }
11 }
12 return dp[n][capacity];
13}

Base caseComputedBeing readAnswer

The code, the trap, the variations

zero-one-knapsack.ts

1function knapsack(weights, values, capacity) {
2 const n = weights.length;
3 const dp = Array.from({ length: n + 1 }, () => new Array(capacity + 1).fill(0));
4 // row 0: no items, so value 0 at every capacity
5 for (let i = 1; i <= n; i++) {
6 const w = weights[i - 1], v = values[i - 1];
7 for (let c = 0; c <= capacity; c++) {
8 dp[i][c] = dp[i - 1][c];
9 if (w <= c) dp[i][c] = Math.max(dp[i][c], v + dp[i - 1][c - w]);
10 }
11 }
12 return dp[n][capacity];
13}

Where people go wrong

Packing greedily by value per unit of weight. (5, 7) has the best ratio, 1.4, so greedy packs it first; (3, 4) and (4, 5) no longer fit beside it, (1, 1) does, and greedy stops at 8 with one unit of capacity unused. The table's 9 comes from (3, 4) and (4, 5), a pair greedy never considers once (5, 7) is in. Greedy by ratio is correct for the fractional knapsack, where items can be cut; with whole items it is not, and that difference is the reason this problem needs a table.

Allow each item to be taken any number of times.
That is unbounded-knapsack. The take option reads the current row, dp[i][c - w_i], because the item is still available after being taken, and the state now allows each item any number of times. Row 0, the max and the row-by-row, left-to-right fill stay.
Require the knapsack to be filled to exactly its capacity.
Only row 0 changes: dp[0][0] = 0 and every other row-0 cell becomes minus infinity, meaning that capacity cannot be filled exactly with no items. The max then never builds on an impossible load, and the recurrence is untouched.
Report which items make up the best load.
The fill is identical. Afterwards, walk back from the answer cell: where a cell equals the one above, the item was not needed; where it differs, the item is in. printing-items-in-zero-one-knapsack teaches that walk.

Weighted Job Schedulling Printing Items in 0/1 Knapsack