The Knapsack Problem
The 0/1 knapsack problem asks: given items each with a weight and a value, and a bag that holds a fixed capacity, which subset of items maximizes total value without exceeding the capacity? Each item is taken once or not at all.
Dynamic programming
A greedy approach fails because the best value per weight does not guarantee the best combination. Instead build a table indexed by item and remaining capacity:
- For each item, decide to skip it and keep the value from earlier items, or take it and add its value plus the best result for the leftover capacity.
- The answer is the maximum of those two choices.
This runs in time proportional to the number of items times the capacity, which is pseudo polynomial because it depends on the numeric capacity, not just the item count.
Space saving
You only need the previous row to compute the next, so a one dimensional array updated from high capacity down to low capacity works and uses far less memory.
Key idea
At every item you choose take or skip, and dynamic programming remembers the best value for each remaining capacity.