The knapsack problem selects whole items with different weights and values to maximize value without exceeding a fixed capacity. In the 0/1 variant, each item is either taken once or left behind. section 8.1
Figure 8.1. The robber must carefully decide what items to steal because the capacity of the knapsack is limited.
A limited-capacity theft scenario makes the competing goals—value and available weight—immediately visible. section 8.1
Solve the problem incrementally with a dynamic-programming table:
- Represent each item with a name, weight, and value. section 8.1
- Treat each table cell as the best value available for a capacity and a prefix of the item list. section 8.1
- For each item and capacity, keep the previous value when the item does not fit; otherwise compare excluding it with including it. section 8.1
- Reconstruct the chosen items by walking backward through the table and subtracting the weight of every item whose inclusion changed the value. section 8.1
A 75-pound selection
A candidate list includes a television, candlesticks, stereo, laptop, clothing, jewelry, and other household goods. Calling knapsack(items: items, maxCapacity: 75) chooses the highest-value combination that fits, rather than testing every subset. section 8.1
