Dynamic Programming with a Capacity: Knapsack
The knapsack table is indexed by item and by remaining capacity, which makes its size depend on the numbers in the input rather than on how many there are. That is why the method is called pseudo-polynomial and why doubling the weights doubles the work.
What a learner can do afterwards
- Fill a knapsack table for five items and read off which items were taken
- Explain why the table has capacity as one of its axes
- Say why an input written with larger numbers costs more without holding more items
1 · Read
The knapsack table is indexed by item and by remaining capacity. Each row adds one item to the choice, each column a capacity. The cell asks: take this item or skip it.
Three items weigh 2, 3, and 4 with values 3, 4, and 5. Capacity is 5. The table fills, the corner reads 7, and the traceback takes the first two items. Weight 5, value 7.
Capacity is an axis because the choice depends on room left. The same item is worth taking with space to spare and wrong when the bag is nearly full. The column carries that context.
The table size follows the numbers, not just the item count. Doubling all weights doubles the columns and the work. That number-driven cost is why the method is called pseudo-polynomial.
Index by item and capacity, read the corner, and note the cost follows the numbers.
2 · Watch
Take it off screen
Where it sits
8 questions wait behind this lesson, each with its answer explained. Every answer feeds the sky: stars light as they are learned, and dim when it is time to come back.