You have a bag that holds a fixed capacity of weight and a pile of items, each with a value and a weight. The fractional knapsack problem asks for the most total value you can carry — and crucially, you may take *any fraction* of an item, not just all-or-nothing. That one freedom is what makes a simple greedy rule provably optimal: always grab from the item with the best value-per-weight first.
Density is the only thing that matters
Think of each item as a fluid with a *density* = value ÷ weight. To maximise value in a fixed volume, you pour in the densest fluid first, then the next densest, topping off the bag with a partial pour of whatever comes next.
The algorithm
1Compute each item's density = value / weight.
2Sort items by density, highest first.
3Walk the sorted list: if the whole item fits in the remaining capacity, take it whole and subtract its weight.
4When the next item is too big to fit, take just the fraction that fills the bag exactly — remaining_capacity / weight of it — and stop.
Worked example
Capacity = 50. Three items: A(value 60, weight 10), B(value 100, weight 20), C(value 120, weight 30). Their densities are A = 6, B = 5, C = 4, so the greedy order is A, then B, then C.
capacity left = 50
take A whole : weight 10, value 60 -> cap left 40
take B whole : weight 20, value 100 -> cap left 20
take C frac : 20/30 of it = 2/3 * 120 = 80
--------------------------------------------------
total value = 60 + 100 + 80 = 240
The bag ends exactly full at weight 50, carrying 240 of value — the best possible. Taking C whole instead of B would have been worse, because B's weight buys more value per unit.
This greedy fails for 0/1 knapsack
If you are *not* allowed fractions — each item is take-it-or-leave-it — the density rule can be beaten, because you might be forced to waste leftover capacity. That harder problem needs dynamic programming or branch and bound, not greed.
OperationTimeSpace
Sort by density · the dominant costO(n log n)O(n)
Greedy fill · one pass over sorted itemsO(n)O(1)
Check yourself
Why is the greedy value-per-weight rule optimal for fractional knapsack but not for 0/1 knapsack?
