the fractional knapsack

You are a thief with a sack that holds a fixed weight, standing before piles of valuable goods — gold dust, silver shavings, jewels. Each good has a total value and a total weight, and crucially you may take ANY fraction of a pile, not just whole units. Which goods, and how much of each, maximize the value you carry off? This is the fractional (divisible) knapsack.

The greedy rule is to rank goods by value density — value divided by weight, the worth of one kilogram — and fill the sack from the densest down. Take all of the densest good, then all of the next densest, and so on, until you reach the one that no longer fits whole; take just enough of THAT good to top the sack off exactly to its capacity. Because goods are divisible, you never waste capacity and you never carry a less-valuable kilogram while a more-valuable kilogram is still available. The exchange argument: if any optimal packing carries some kilogram of a lower-density good while a kilogram of a higher-density good is left behind, swap that lower-density kilogram for the higher-density one — same weight, strictly more value, contradicting optimality. Hence greedy by density is optimal. After an O(n log n) sort by density, the fill is O(n).

Fractional knapsack is the textbook positive example that pairs with its famous failure twin. Its 0/1 cousin — where you must take each item whole or not at all — does NOT yield to this greedy rule, because once items are indivisible you can be forced to leave a sliver of capacity empty, and a high-density item may be too heavy to fit while two lower-density items together would have done better. Divisibility is the hinge. The very same density-greedy that is provably optimal here can be provably suboptimal one assumption away.