Suppose you want the most valuable set of items that fits in a knapsack. Instead of tackling the full knapsack at once, draw a grid for smaller versions of the problem. Start with an empty grid; filling its cells builds toward the answer. section 11.3
For a knapsack grid:
- Give each row an item. A row considers the items available up to that point. section 11.3
- Give each column a capacity, such as 1, 2, 3, or 4 lb. Each cell records the best value for that capacity and stage of the problem. section 11.3
The first row
A guitar weighs 1 lb and is worth $1,500. With only the guitar available, it fits in the 1 lb knapsack, so that cell has a value of $1,500. It also fits in the larger capacities along that row. section 11.3
Choose the columns carefully. A grid with only whole-pound capacities cannot answer what fits in 3.5 lb of remaining space. Adding a 0.5 lb necklace means the grid needs finer capacity steps. section 11.8
The same grid idea can serve other dynamic programming problems. To compare words for a longest common substring, use the two words as axes; each cell represents a smaller comparison and holds a substring length. What the cells mean—and how to calculate them—depends on the problem. section 11.15 section 11.20
