The 0-1 knapsack problem chooses each item at most once, maximizing total value without exceeding a fixed capacity. A brute-force search considers every subset, so the number of combinations grows explosively as items are added. section 1.3.3
The main design choices are:
- Use dynamic programming when capacity is sufficiently limited: the pseudo-polynomial solution takes time proportional to the capacity multiplied by the number of items. section 1.3.3
- Recognize the trade-off: 0-1 knapsack is NP-complete, so no polynomial-time algorithm for finding an optimal solution is known. section 1.3.3
- Question the constraints before optimizing: allowing fractional quantities changes the problem and enables a greedy strategy based on value per unit weight. section 1.3.4
Packing a mission crate
With 62 possible items and a 1000-kilogram capacity, dynamic programming requires about 1000 × 62 capacity-item steps instead of checking 2^62 combinations. If fractional quantities and repacking are allowed, selecting by calories per kilogram yields peanut butter, rice, wheat flour, strawberry jam, and 230 kilograms of beans, totaling 3,342,800 calories. section 1.3.3 section 1.3.4
The problem illustrates a broader algorithm-design lesson: preserve necessary constraints, but test whether relaxing an expensive constraint produces a sufficiently valuable and cheaper solution. section 1.3.5
