Fractional Knapsack
Fractional Knapsack: items have value and weight; capacity is W. You may take fractions of items. Maximize total value.
- 1 <= n <= 10⁵
- 1 <= W <= 10⁵
- 1 <= value[i], weight[i] <= 10⁴
- Fractions of an item may be taken
Intuition
In the fractional knapsack problem, items have a value and a weight, the sack holds W, and — crucially — you may take part of an item. That one allowance changes the problem completely compared with 0/1 knapsack, which needs dynamic programming.
Think about what a single kilogram of capacity is worth. If you spend it on an item, you get value / weight worth of value for that kilogram. So every item has a density, and the question becomes how to spend W kilograms to buy the most value.
With fractions allowed, there is no packing puzzle left. You simply buy the densest thing available until you run out of capacity:
- Sort by value ÷ weight descending, take whole items while they fit, then take the exact fraction of the next one that fills the remaining space.
The reason greedy is provably optimal here is worth holding onto. Suppose some solution carries a kilogram of a lower-density item while a higher-density item remains partly untaken. Swap that kilogram — total weight is unchanged and total value strictly increases. So no arrangement that violates density order can be optimal.
That argument depends entirely on divisibility. In 0/1 knapsack you cannot swap a single kilogram, and greedy fails: a dense small item can block a much more valuable pairing.
Fractions are what make greedy legal here. Because you may take part of an item, filling the bag with the best value-per-unit-weight first is provably optimal — there's never a reason to leave a denser item behind. The instant items become indivisible (0/1 knapsack), that argument collapses and you need DP. Spotting whether splitting is allowed decides the entire approach.
Approach
Before reading on: price up what sorting first costs here, then ask why the locally best choice is safe to commit to and never revisit. Aim for O(n log n) time and O(1) space.
Compute each item's value density
Density is value / weight — what one unit of capacity buys if spent on that item. This single number is what makes the items comparable, since raw value ignores the space consumed and raw weight ignores the payoff.
Sort by density, highest first
Order the items so the best value per kilogram comes first. Sorting dominates the runtime, and everything after it is a single linear sweep.
Take whole items while they fit
Walk the sorted list, adding each item entirely while its weight is within the remaining capacity. Subtract its weight and add its full value. No decision is needed here — density order already settled it.
Take a fraction of the item that overflows
When the next item is too heavy, take exactly the fraction that fills the sack: remaining / weight of it, contributing that fraction of its value. The sack is now full, so stop immediately — every later item has lower density and there is no space left anyway.
Know why greedy fails for 0/1 knapsack
The proof relies on swapping a kilogram of low-density cargo for high-density cargo. With indivisible items that swap is impossible, and greedy can be arbitrarily bad — which is why the 0/1 version needs a DP table instead.
Cost of the approach
Sorting is O(n log n) and the sweep is O(n), so sorting dominates. Space is O(1) beyond the sort. Use floating point for the fractional part, or exact rational arithmetic if the problem demands precision.
Solution & live demo
Common pitfalls
Sorting by value instead of value-to-weight ratio
items.sort(key=lambda x: x[0], reverse=True)
items.sort(key=lambda x: x[0] / x[1], reverse=True)
A high-value item can be so heavy that it crowds out several lighter items worth more in total. What the bag is really spending is capacity, so the quantity to maximise is value per unit of weight.
Skipping an item that doesn't fit whole
if W >= w:
total += v; W -= w
else:
continueelse:
total += v * W / w
breakThis is the difference between the fractional problem and 0/1. Once an item doesn't fit entirely, you take the portion that does — and since the bag is then exactly full, no later item can be added, so you stop.
Integer division on the partial take
total += v * W // w
total += v * W / w
The whole point of the fractional variant is that the answer is generally not an integer. Floor division silently discards the remainder of the last, partially-taken item.
Edge cases
Take remaining/weight of it — the only fractional take, always the last.
Everything fits; answer is the total value.