Dynamic Programming with a Capacity: Knapsack
A 0/1 knapsack table stores the best value for an item prefix and an allowed capacity. With integer weights, its O(n(W+1)) work depends on numeric capacity W, which may be large compared with the number of bits used to write it. This is pseudo-polynomial time.
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
- Explain why increasing numeric capacity W adds table columns with item count fixed, and why W can be large compared with its binary encoding length
1 · Read
As with two-string tables, define both indices. In 0/1 knapsack, each item can be taken at most once. Use positive integer weights and nonnegative values. K(i,c) is the best total value using the first i items with total weight at most c. Rows count available items; columns give allowed capacity from 0 to W. Initialize K(0,c)=0 and K(i,0)=0.
For item i with weight w_i and value v_i, skipping gives K(i-1,c). If w_i is at most c, taking gives v_i+K(i-1,c-w_i). Store the larger value. If the item does not fit, use only the skip value. Both choices use the previous row, which prevents taking item i twice. Fit alone does not mean taking the item is best.
For a small instance, you can list feasible subsets and compare totals. Items 1, 2 and 3 have weights 2, 3 and 4, and values 4, 5 and 6. Capacity is 5. Items 1 and 2 give weight 5 and value 9; other pairs do not fit. The table agrees: row 2 at capacity 5 compares skip value 4 with take value 5+K(1,2)=9. Row 3 compares 9 with 6+K(2,1)=6, keeping 9.
The final value is K(n,W). To recover items, compare K(i,c) with K(i-1,c). If equal, you may skip item i and move up. Otherwise take item i, subtract w_i from c, and move up. Repeat until no items remain. A tie may allow more than one optimal set. The final value alone does not identify its items.
The (n+1)(W+1) cells take constant work each in the usual arithmetic model. O(n(W+1)) bounds work by a constant times n(W+1) for large inputs. Input size counts all encoded bits. For W>0, log2(W) is the exponent in 2^log2(W)=W. Rounded down, plus 1, it counts W's binary bits. Thus W can grow exponentially in its bit length. Work is polynomial in n and W, not binary input size: pseudo-polynomial.
Doubling weights alone leaves the columns unchanged if capacity W stays fixed. Doubling both weights and capacity changes W+1 columns to 2W+1, roughly twice as many for large W. The number of item rows stays the same. This scaling preserves which subsets fit, but increases the work of the uncompressed capacity table.
Compare skip with take-once in each capacity state. Trace back for the items. Table work follows numeric capacity, not just its encoded length.
Original lesson, questions, worked solutions and flashcards written for this dataset.
2 · Watch
En anglaisTake it off screen
Where it sits
Learn first
Optional connections
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.