The knapsack algorithm selects a highest-value subset of indivisible items without exceeding a capacity or budget. Each item is an all-or-nothing choice: take it or leave it. section 7.0
Testing every combination takes exponential time, O(2ⁿ). Dynamic programming avoids repeating work by tracking earlier decisions and storing solutions for smaller item sets and capacities. section 7.0
Scheduling workloads
With an 8-GB limit, applications needing 1, 2, and 5 GB have priority values 2, 3, and 6. Selecting them uses all 8 GB and gives a total priority of 11. section 7.2
The same framework applies to loading indivisible freight under a vehicle’s payload limit. section 7.2
