Dynamic programming solves a large problem by solving overlapping smaller subproblems, storing their results, and combining them. It replaces the knapsack problem’s exponential brute-force search with a table indexed by item count and capacity. section 8.1
A table-driven knapsack solution proceeds in stages:
- Represent each item with a name, weight, and value. section 8.1
- Create a table whose rows represent available items and whose columns represent capacities. section 8.1
- For each item and capacity, keep the previous best value when the item does not fit; otherwise compare skipping it with taking it. section 8.1
- Walk backward through the completed table, detecting changed values to reconstruct the selected items and their remaining capacity. section 8.1
A constrained theft problem
Given items with different weights and values, a thief may take each item once. For a 75-pound capacity, the algorithm evaluates every item-capacity combination without enumerating every subset, then returns the most valuable feasible selection. The same pattern applies to allocating a limited athletic budget among teams with expected returns. section 8.1 section 8.5
Table 8.1. An example of a knapsack problem of three items
| Weight |
0 |
1 |
2 |
3 |
|---|---|---|---|---|
| Matches (1 lb, $5) | 0 | 5 | 5 | 5 |
| Flashlight (2 lbs, $10) | 0 | 5 | 10 | 15 |
| Book (1 lb, $15) | 0 | 15 | 20 | 25 |
A small three-item table makes the recurrence visible: each cell records the best value for a particular capacity and set of available items. section 8.1
