An NP-complete problem is a decision problem whose proposed solutions can be verified quickly, yet whose optimal solution has no known polynomial-time algorithm. The 0-1 knapsack problem illustrates the practical consequence: exploring every subset can become impossibly slow as the number of items grows. section 1.3.3
When a problem is NP-complete, evaluate the constraints before abandoning the task:
- Avoid exhaustive search when combinations grow explosively; 62 items already produce billions of billions of possible combinations. section 1.3.3
- Exploit bounded numeric inputs when available: dynamic programming solves the knapsack instance in proportion to capacity times item count, rather than all subsets. section 1.3.3
- Question restrictive assumptions: allowing repeated or fractional item quantities changes the problem and can enable a greedy algorithm. section 1.3.4
Cargo selection
A launch team must select goods for a 1,000-kilogram crate while maximizing calories. With 62 indivisible items, exhaustive subset search is impractical, but capacity-based dynamic programming requires roughly 1,000 × 62 steps. If fractional quantities are allowed, sorting by calories per kilogram and filling the remaining space greedily yields an easier variant. section 1.3.3 section 1.3.4
