Medium Problemsknapsackreconstruction

Printing Items in 0/1 Knapsack

Given the same setup as the 0-1 knapsack, with item weights, values, and a fixed capacity, find the best achievable value and also report which specific items make up one optimal selection.

Do this lesson first: coin change

Example input

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

Expected output

9, from items 2 and 3 (weights 3 and 4, values 4 and 5)

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.

fill: dp[i][c] = max(dp[i - 1][c], v_i + dp[i - 1][c - w_i]); walk: item i is in exactly when dp[i][c] != dp[i - 1][c]

The fill's last decision is zero-one-knapsack's: item i is either out (the cell above) or in (v_i plus the cell w_i columns to the left in the row above). The walk asks the same question in reverse, about a cell that is already filled. If dp[i][c] equals dp[i - 1][c], the value here is reachable without item i, so leave it out and step up. If they differ, the only way this cell got bigger than the one above is by taking item i, so record it and step to dp[i - 1][c - w_i], the cell the take option read. Each step settles one item and climbs one row, so the walk takes n steps.

Row 0 is all 0s and the fill runs row by row from the top, as on zero-one-knapsack. The walk then runs the other way: it starts at the answer cell, dp[n][capacity], climbs one row per step to row 0, and moves left only when it records an item. It reads cells and writes none, which is why the animation stops at the answer: every animated step reads cells in order to write one, and the walk writes nothing. In drive mode only the last row's comparisons are gated, because the walk starts in the last row and the fill itself is zero-one-knapsack's lesson.

Two passes: fill the (n + 1) × (capacity + 1) table, then walk it in n steps. The walk needs the WHOLE table. The one-row trick that saves space on zero-one-knapsack overwrites row i - 1 while computing row i, so by the end only the last row survives and the comparison the walk depends on, dp[i][c] against dp[i - 1][c], is gone. Keeping every row is the price of reporting the items. If memory is tight, store one bit per cell saying whether the take option won outright; that is enough to walk back, and it costs a bit rather than a number per cell.

Time O(n × capacity) to fill, plus O(n) to walk backSpace O(n × capacity); the walk needs every row's comparison, kept either as the full table or as one bit per cell

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 all 0s and the fill runs row by row from the top, as on zero-one-knapsack. The walk then runs the other way: it starts at the answer cell, dp[n][capacity], climbs one row per step to row 0, and moves left only when it records an item. It reads cells and writes none, which is why the animation stops at the answer: every animated step reads cells in order to write one, and the walk writes nothing. In drive mode only the last row's comparisons are gated, because the walk starts in the last row and the fill itself is zero-one-knapsack's lesson.

Rows ↓
Cols →

0

1

2

3

4

5

6

7

none

0

w2 v3

0

3

w3 v4

0

3

4

7

w4 v5

0

3

4

5

7

8

9

w5 v6

0

3

4

5

7

8

9

Rows ↓row i: may use the first i items

Cols →capacity c: best value that fits

printing-items-in-zero-one-knapsack.ts

1function knapsackItems(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 const picked = [];
13 for (let i = n, c = capacity; i >= 1; i--) {
14 if (dp[i][c] !== dp[i - 1][c]) {
15 picked.push(i);
16 c -= weights[i - 1];
17 }
18 }
19 return { best: dp[n][capacity], items: picked.reverse() };
20}

Base caseComputedBeing readAnswer

The code, the trap, the variations

printing-items-in-zero-one-knapsack.ts

1function knapsackItems(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 const picked = [];
13 for (let i = n, c = capacity; i >= 1; i--) {
14 if (dp[i][c] !== dp[i - 1][c]) {
15 picked.push(i);
16 c -= weights[i - 1];
17 }
18 }
19 return { best: dp[n][capacity], items: picked.reverse() };
20}

Where people go wrong

Walking a space-optimised table. Fill with the single row zero-one-knapsack's execution describes and the rows the walk compares no longer exist, so there is nothing to compare dp[i][c] against; the walk needs the full grid, or one stored bit per cell. The other mistake is deciding an item is in because it FITS in the capacity still left. At capacity 7 that rule takes item 4 first, since it weighs 5, then item 1 in the 2 that remain, which reaches 9 here only because items 1 and 4 happen to be the second optimal selection. At capacity 6 the same rule takes item 4, finds nothing else fits in the 1 that remains, and reports a value of 6 against the table's 8. The walk must compare each cell with the one above it, not with the item's weight.

Report every optimal selection, not just one.
The fill stays. At a tie, where leaving item i out and putting it in give the same value, the walk branches both ways instead of stepping up. At capacity 7 that finds items 2 and 3 and also items 1 and 4, so the walk becomes a search over the ties.
Report the items of an unbounded knapsack, or the pieces of cutting-a-rod.
The same walk with one change: taking an item stays in the SAME row and steps left by its weight, because the item may be taken again. Step up a row only when the cell equals the one above.
Among optimal selections, prefer the one with the fewest items.
The walk alone cannot see item counts, so the fill has to carry them: compare (value, minus the item count) as a pair, larger value first and fewer items on a tie. The walk is unchanged and then lands on the fewest-items selection.

0-1 Knapsack Problem Unbounded Knapsack