Capacity is the maximum total weight that selected items may occupy. In the 0/1 knapsack problem, each item is either taken once or left behind; no item may be split. section 8.1
Dynamic programming treats capacity as a sequence of subproblems. A table evaluates capacities from 0 through the limit for progressively larger sets of items, avoiding the exponential cost of checking every subset. section 8.1
A three-pound capacity
For a 3 lb. knapsack, the table compares capacities 0, 1, 2, and 3. With Matches, Flashlight, and Book, the best values are 0, 15, 20, and 25 respectively. section 8.1
Figure 8.1. The robber must carefully decide what items to steal because the capacity of the knapsack is limited.
Use the figure to visualize capacity as the limited space forcing a choice among competing items. section 8.1
