Imagine a bag that holds 35 pounds. You have several items, each with a weight and a value. Which ones should you take? The knapsack problem asks you to choose items that fit within the capacity while making their combined value as high as possible. section 10.2
Why the obvious choice can lose
A tempting strategy is to take the most expensive item that fits, then repeat. But taking a stereo worth $3,000 leaves no room for anything else, while a laptop and guitar together are worth $3,500. A greedy choice can be useful when a good-enough answer will do, but it does not always find the best one. section 10.2
To find the best choice, dynamic programming works up from smaller knapsacks. Draw a grid with items as rows and capacities as columns. At each cell, ask whether taking the current item gives a better result than leaving it out. In a 4-pound example, a 1-pound guitar worth $1,500 fits in the first cell; the remaining cells build on smaller decisions. Even when the best answer contains several items, its smaller solutions can build on still smaller ones. section 11.3 section 11.12
The same question comes up when the limit is time rather than weight. For a two-day trip, give each place a time cost and a desirability rating, then use a grid to choose what to visit. section 11.10
