Card 02/ 09
Fill the Knapsack Table One Item at a Time
Each row adds one item, and each cell keeps the better of leaving it out or putting it in.
Filling a knapsack table means adding the items one row at a time and, in every cell, keeping the larger of the value without the new item and the value with it. This walkthrough fills the table for three parcels and a 6 kilo bag, reads the best value from the last cell, and walks back up the rows to find which parcels make it.
The parcels are A (2 kilos, £3), B (3 kilos, £5) and C (4 kilos, £6). Each row is one more parcel, each column a capacity from 0 to 6 kilos, and the cell holds the most value those parcels can earn in that much room.
Before the table: what is the best value for 6 kilos, and which parcels give it?
£9, from A and C, which weigh 6 kilos together. The table below reaches it cell by cell.
Filling best[i][c] for parcels A, B and C and capacities 0 to 6
Add A
The row for no parcels is all 0. A weighs 2, so capacities 0 and 1 cannot take it and copy the 0 above. From capacity 2 up, taking A earns 0 + 3 = 3, more than skipping it. Cells marked [ ] are those where taking the new parcel won.
| Items | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|---|
| None | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| A | 0 | 0 | [3] | [3] | [3] | [3] | [3] |
Add B
B weighs 3. At capacity 3, taking it earns the cell above capacity 0, which is 0, plus 5, against 3 for skipping. At capacity 5, taking it earns the cell above capacity 2, which is 3, plus 5: 8, both A and B. Capacity 2 is too small for B and keeps 3.
| Items | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|---|
| None | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| A | 0 | 0 | 3 | 3 | 3 | 3 | 3 |
| A, B | 0 | 0 | 3 | [5] | [5] | [8] | [8] |
Add C
C weighs 4. At capacity 4, taking it earns 0 + 6 = 6 against 5. At capacity 5, taking it earns 0 + 6 = 6 against 8, so the cell keeps 8 and skips C. At capacity 6, taking it earns the cell above capacity 2, which is 3, plus 6: 9 against 8.
| Items | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|---|
| None | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| A | 0 | 0 | 3 | 3 | 3 | 3 | 3 |
| A, B | 0 | 0 | 3 | 5 | 5 | 8 | 8 |
| A, B, C | 0 | 0 | 3 | 5 | [6] | 8 | [9] |
The answer is the last cell, best[3][6] = 9, which a run confirmed. To find the parcels, start at that cell and walk back up the rows. The cell for C at capacity 6 was a take, so C is packed and the room left is 6 − 4 = 2. In row B, capacity 2 was not a take, so B is not packed. In row A, capacity 2 was a take, so A is packed, leaving 0. The parcels are A and C, as the run printed.
The recovery works because the full table remembers, for each item and capacity, which choice won. It is why the two-dimensional table is worth keeping when the question asks which items to take, even though the value alone needs only one array, as Knapsack in Python, Java and TypeScript shows.
← → move through sections and cards