Fractional Knapsack
Items have weights and values, and a knapsack has capacity W. You may take any fraction of an item. Maximise the total value carried.
- 1 ≤ n ≤ 10^5
- 1 ≤ weight[i], value[i] ≤ 10^6
- 1 ≤ W ≤ 10^9
- Fractions allowed — the divisibility that makes greedy optimal
- Value per unit weight is the natural ranking
- Fill in ratio order until capacity runs out
When a locally best choice (earliest finish time, largest ratio, farthest reach) can be proved never to hurt the global optimum, you can commit to it without exploring alternatives and get O(n log n) from sorting. The proof usually comes via an exchange argument; if you cannot sketch one, suspect DP instead.
Compute each item's value-to-weight ratio and sort items by it in descending order. Take whole items in that order while they fit; when the next item does not fit, take the fraction that exactly fills the remaining capacity and stop. Because any unit of capacity is best spent on the densest remaining item, no rearrangement can improve the total.
- Quickselect on the ratio finds the cut-off item in O(n) expected time. The 0/1 variant is NP-hard and requires DP.