Proving Fractional Knapsack Correctness
You'll learn why sorting items by value-to-weight ratio and greedily taking them produces the optimal solution for the fractional knapsack problem.
The Core Idea
In the fractional knapsack problem, you have a knapsack with weight capacity and items with values and weights. You can take fractions of items. The greedy strategy is: sort items by value-per-weight ratio (highest first), then fill the knapsack greedily until full.
But why is this optimal?
The Exchange Argument Proof
Imagine you have a solution that doesn't follow the greedy ordering—it includes some item j with lower ratio before exhausting item i with higher ratio.
The exchange: Swap some amount of item j for the same weight of item i. Since item i has a better value-to-weight ratio, this swap strictly increases total value while maintaining the same weight.
Repeat this exchange until your solution matches the greedy solution. Each swap improves (or maintains) value, so the greedy solution must be at least as good as any other solution.
Why This Works
Think of items as liquids with different "value densities." You're filling a container. Would you ever choose to pour in a less valuable liquid when a more valuable one is available? Of course not! You'd pour the most valuable liquid first until you run out, then the next best, and so on.
The fractional nature is crucial—you can take exactly as much as needed to fill capacity optimally. The greedy choice property holds because taking the highest-ratio item first never prevents you from achieving the optimal solution.
Key Takeaway: The fractional knapsack greedy algorithm is correct because any deviation from sorting by value-to-weight ratio can be improved by exchanging lower-ratio items for higher-ratio ones, proving the greedy solution is optimal.