138. Fractional Knapsack Problem

Given n items, each with a weight and a value, and a knapsack of capacity W, find the maximum total value obtainable, where any fraction of an item may be taken. Print the answer with exactly one decimal place.

Input: The first line contains an integer n, the number of items. Each of the next n lines contains two space-separated integers, an item's weight and value. The final line contains W, the knapsack capacity. Output: Print the maximum total value obtainable, formatted with exactly one decimal place.

1 <= n <= 10^5, items are given as n (weight, value) pairs

The ability to take FRACTIONS of items is exactly what makes greedy provably optimal here - in the 0/1 version (whole items only), the same greedy ratio-based strategy can actually give a WRONG answer, which is why that variant needs dynamic programming instead.

Fill a knapsack of limited capacity with items (or fractions of items) to maximize total value. Brute force: Try every possible combination of full/partial item selections directly - this is unnecessary given that a simple greedy ratio-based ordering is provably optimal for the FRACTIONAL version of this problem (unlike the 0/1 knapsack, which genuinely needs DP). Optimised: Because items can be taken in ANY fraction, always filling with the highest value-per-weight ratio first is provably optimal - there's no benefit to ever taking a lower-ratio item before a higher-ratio one is fully exhausted, since fractional taking means you never 'waste' capacity choosing a worse ratio.

Compute the value-to-weight ratio for every item, then repeatedly scan the remaining items to find the one with the highest ratio, take as much of it as capacity allows, and remove or partially consume it before repeating. This already uses the greedy insight that higher-ratio items should be prioritized, but finding the best remaining item by linear scan each round costs O(n) per selection instead of sorting once up front. Time: O(n^2) Space: O(n)

Sort all items once by value-to-weight ratio in descending order. Walk through them, taking the whole item if it fits, or the exact fraction that fills the remaining capacity, then stop. Because fractional taking is allowed, always preferring the highest-ratio item available is provably optimal (an exchange argument shows swapping any lower-ratio unit for a higher-ratio one never decreases total value), and sorting up front avoids repeated scans for the maximum. Time: O(n log n) Space: O(n)

Try every order in which items could be added to the knapsack and, for each order, greedily fill the knapsack by taking as much of each item as fits before moving to the next, keeping the best total value found across all orders. This is correct because the true optimal filling order is among those tried, but enumerating all n! orderings is wildly impractical beyond a handful of items. Time: O(n! * n) Space: O(n)

1. Sort items by VALUE-PER-UNIT-WEIGHT (value / weight) in descending order. 2. Take as much as possible of the best-ratio item first (its entire weight, if it fits). 3. Move to the next-best ratio item, repeating, until the knapsack is full - taking only a FRACTION of the last item that doesn't fully fit.

Time: O(n log n), dominated by sorting items by their value-per-weight ratio. Space: O(1) extra space beyond the sorted item list.

W = 0 (answer 0.0), W large enough to take every item fully, and n at its maximum of 10^5 to confirm the sort-by-ratio approach runs efficiently.

Be ready to clearly distinguish this from the 0/1 Knapsack problem (which requires DP, since items can't be fractionally split there) - a very common point of confusion, and correctly identifying which variant applies is the key first step.