Fractional knapsack: greedy by value per kilogram

The idea: fill a bag when you may cut the items

A bag holds at most W kilograms. Each item has a weight w and a value v. In the fractional knapsack problem you may take any part of an item, like flour or gold dust: half of an item weighs half and is worth half. In the 0/1 knapsack problem each item is taken whole or left behind. The page runs the same greedy rule on both, side by side, and then shows the best whole-item load.

The greedy rule

Work out each item's value per kilogram, v / w. Sort the items from the largest ratio to the smallest. Then go down the list: take the whole item while it fits, and when the next item does not fit, take only the part that fills the bag and stop. At most one item is cut. Sorting costs O(n log n) and the pass is O(n).

With the CLRS items (A 10 kg $60, B 20 kg $100, C 30 kg $120, W = 50) the ratios are $6, $5 and $4 per kg. Greedy takes A and B (30 kg, $160), then 20 of C's 30 kg, worth 2/3 × $120 = $80: $240 in all. (Demo: CLRS items, W = 50) With seven items and W = 15 it takes E, A, F, C and G whole (13 kg, $52) and cuts 2/3 of B for the last 2 kg: $55.33. (Demo: seven items, W = 15)

Why value per kilogram is optimal

Think of the bag as W slots of one kilogram each. Every kilogram of item i is worth v_i / w_i, whatever else is in the bag. Take any load that holds a kilogram of a lower ratio while a kilogram of a higher ratio is left outside. Swap them: the weight stays the same and the value goes up (or stays the same on a tie). So a best load can always be changed, swap by swap, into the greedy load without losing value. This is an exchange argument, the usual way to prove a greedy choice safe.

Other sort keys fail, even with cutting

The order matters. Sorting by the highest value or by the lightest weight sounds reasonable but can fill the bag with cheap kilograms. On the seven items with W = 15:

sort by	order	fractional value
value per kg	E, A, F, C, G, B, D	✓ $55.33
highest value	F, C, A, D, …	✗ $47 (4/7 of D, at $1/kg)
lightest first	E, G, A, B, F, C, D	✗ $54 (B at $1.67/kg in, 1 kg of C out)

(Demo: wrong rule, highest value first; Demo: wrong rule, lightest first)

The same greedy on 0/1 knapsack

With whole items the swap argument breaks: you can't swap one kilogram of an item, only the whole item, and a big item may not fit into the gap that is left. Greedy then leaves the bag partly empty. In the CLRS example it takes A and B and must skip C, for $160, while B + C gives $220. It can be much worse: with A 1 kg $2 and B 10 kg $10 in a 10 kg bag, greedy takes A first (the better ratio) and then B no longer fits: $2 against $10. (Demo: a 0/1 trap, W = 10)

	fractional knapsack	0/1 knapsack
items	any part of an item	whole or nothing
greedy by value/kg	✓ optimal	✗ can be far off
exact method	sort + one pass, O(n log n)	DP table, O(nW); NP-hard in general

The fractional answer is never below the 0/1 answer, because every whole-item load is also a fractional load. Branch-and-bound solvers for 0/1 knapsack use the fractional value as an upper bound to prune branches.

See also 0/1 Knapsack, which fills the DP table that finds the best whole-item load, and Greedy vs DP Coin Change, another case where greedy works for some inputs only. Other greedy choices that are provably optimal: Interval Scheduling and Huffman Coding. Greedy by price per inch fails on Rod Cutting.

Ranking items by value per unit of capacity is the same move as trade by Comparative Advantage: each good is made where its opportunity cost is lowest.

What the page leaves out

Weights are whole kilograms and there are at most seven items, so the bars stay readable. The page finds the best 0/1 load by trying every subset instead of animating the DP table (the 0/1 Knapsack page does that). It leaves out the O(n) fractional algorithm that finds the cut item with a linear-time median instead of a full sort, bounded and unbounded knapsack, several constraints at once (weight and volume), and approximation schemes for 0/1 knapsack.

References

Continuous knapsack problem (Wikipedia)

Knapsack problem (Wikipedia)

Greedy algorithm (Wikipedia)

Cormen et al., Introduction to Algorithms, section 15.2 (greedy vs dynamic programming)