• 1 ≤ n ≤ 10⁵
• 1 ≤ W ≤ 10⁵
• 1 ≤ value, weight ≤ 10⁴ for every item
• Any fraction of an item may be taken, gaining a proportional value

This is the knapsack you have met before — a weight budget, items with weight and value, maximise the value you carry — with a single relaxation: you may take a fraction of an item. Take a third of an item and you get a third of its value for a third of its weight.

That one change turns a hard problem into an easy one, and understanding why is the whole lesson, because it teaches you exactly when greedy is legal and when it is not.

Recall the ordinary 0/1 knapsack: each item is all-or-nothing. There, a greedy rule like "take the most valuable-per-kilo item first" fails, because taking it might leave an awkward gap of unused capacity that nothing fits into. The items are indivisible, so how well things pack together matters as much as how good they are individually, and no per-item ranking can see that packing. That is why 0/1 needs a dynamic-programming table.

Fractions destroy the packing problem entirely. There is never an awkward gap, because whatever space is left over can always be filled with a slice of the next item. Once "does it fit?" stops mattering, the only thing that matters is efficiency — getting the most value out of each kilo of capacity.

Define each item's value density as value / weight — the value you get per unit of weight. The greedy rule: sort items by density, highest first, and pour capacity into the densest item until it runs out or the bag fills; if an item does not fully fit, take exactly the fraction that fills the remaining space, and stop.

Here is why it is optimal — an exchange argument, the same tool as every greedy page. Suppose an optimal packing contains some amount of a lower-density item while a higher-density item is not fully used. Take a tiny slice of weight w out of the low-density item and replace it with w worth of the high-density item. The weight is unchanged, so the bag is still legal, but the value strictly increases, because the same weight of a denser item is worth more. So the packing was not optimal after all — contradiction. Therefore an optimal packing always fills from densest downward, which is exactly what greedy does. The fractional freedom is what makes the swap always possible: we can move any amount of weight, not just whole items.

def fractional_knapsack(items, capacity):
    # items = [(value, weight), ...]
    items.sort(key=lambda it: it[0] / it[1], reverse=True)   # densest first
    total = 0.0
    for value, weight in items:
        if capacity >= weight:
            total += value                 # whole item fits
            capacity -= weight
        else:
            total += value * (capacity / weight)   # take the fraction that fills the bag
            break                          # bag is now full
    return total

Sorting by density is O(N log N) and dominates; the fill pass is O(N).

Answer 240.0. Notice the last item was split — that slice is what makes fractional knapsack strictly more valuable than the 0/1 version on the same input, where you could not have taken the partial third item.

The reusable idea is not "sort by density" — it is identify what actually constrains the problem, and check whether the greedy swap is legal. For fractional knapsack the constraint reduced to pure efficiency, and arbitrary swaps were legal, so greedy won. For 0/1 knapsack the constraint included packing, swaps were not free, and greedy lost to dynamic programming.

So the transferable habit, reinforced from every page in this section: greedy is only as valid as the exchange argument behind it. Before sorting by any key, ask whether you can locally improve any non-greedy solution toward the greedy one without breaking a constraint. If the improvement is always possible — as it is when you can move fractions — greedy is safe. If some constraint blocks the improvement — indivisibility, ordering, a global balance — greedy probably fails and you need a table.

Recognition signal for the fractional-greedy shape specifically: you are allocating a divisible budget (weight, money, time, bandwidth) across options to maximise a linear return, with no packing or ordering constraint. Sort by return-per-unit-budget and pour. The moment the resource becomes indivisible, or the options interact, that signal switches off.