AlgoScope

Fractional Knapsack

algorithmintermediateTime O(n log n)Space O(n)

If items can be cut, filling a bag is easy: the best thing to carry is whatever is worth the most per kilogram, so sort by value per weight, take the densest items whole, and when the next one does not fit, take exactly the slice that fills the bag. No cleverness can beat that, because any slice you could swap in is less dense than what it replaces. The moment items cannot be cut, this argument breaks and the 0/1 knapsack needs dynamic programming instead.

abcwvv/wtake10203060100120654

Capacity 50. Items sorted by value per unit of weight, best first: 10 kg worth 60, 20 kg worth 100, 30 kg worth 120. Take from the left while they fit whole; the first that does not fit is cut to fill the remaining room exactly.

Check your understanding

The player pauses before each decision in this run and asks what happens next. Here are all 3, with their answers.

  1. Next item weighs 10 and 50 of room is left. How much of it is taken?

    • All of it
    • 50/10 of it
    • None of it

    Answer: All of it. 10 <= 50, so it fits.

  2. Next item weighs 20 and 40 of room is left. How much of it is taken?

    • All of it
    • 40/20 of it
    • None of it

    Answer: All of it. 20 <= 40, so it fits.

  3. Next item weighs 30 and 20 of room is left. How much of it is taken?

    • All of it
    • 20/30 of it
    • None of it

    Answer: 20/30 of it. Only 20 fits, so it is cut there.

How it runs, step by step

  1. Capacity 50. Items sorted by value per unit of weight, best first: 10 kg worth 60, 20 kg worth 100, 30 kg worth 120. Take from the left while they fit whole; the first that does not fit is cut to fill the remaining room exactly.

    Fractional knapsack with capacity 50 and 3 items sorted by ratio.

  2. Item a, 10 kg worth 60 (6 per kg), room 50. It fits whole: take it all, value 60.0, room 40.

    Take item a whole.

  3. Item b, 20 kg worth 100 (5 per kg), room 40. It fits whole: take it all, value 160.0, room 20.

    Take item b whole.

  4. Item c, 30 kg worth 120 (4 per kg), room 20. Only 20 of 30 fits, so take 20/30 of it for 80.0 and the bag is full. Everything after it is left out.

    Take 20 of 30 of item c.

  5. Total value 240.0 with 50 of 50 used. Because items can be split, taking the densest value first can never be beaten: swapping any taken slice for a less dense one loses value. The 0/1 version, where items cannot be cut, needs dynamic programming instead.

    Total value 240.0.

Remember

  • Sort by value per unit of weight; take whole items in that order while they fit.
  • The first item that does not fit is cut to fill the remaining room exactly, and then stop.
  • Greedy is optimal only because slices are allowed; 0/1 knapsack is a different problem.

Topics covered

Related

Where this is used

OptimisationUpper bounds in branch and bound

A solver attacking a 0/1 knapsack relaxes take-it-or-leave-it into take-any-fraction, which is exactly this problem. The fractional answer is never smaller than the integer one, so it is a cheap ceiling: any branch whose bound falls below the best whole solution found so far is discarded unexplored. Dantzig published this bound in 1957 and it is still what a mixed-integer solver computes first at each node.

Web infrastructureSquid's GDSF cache policy

A proxy cache is a knapsack: the disk is the capacity, each object costs its bytes and is worth the traffic it saves. Squid's heap GDSF policy (Greedy-Dual Size Frequency) keeps objects ordered by value per byte and evicts from the cheap end, which is the same density ordering run continuously as new objects arrive. It therefore favours many small popular objects over one large one, raising the object hit rate while lowering the byte hit rate.

CompilersInlining budgets in a compiler

An inliner has a fixed allowance of code growth and far more call sites than it can pay for, so GCC's inter-procedural pass ranks candidates by estimated time saved per unit of extra code size and spends the allowance from the densest down until the unit growth limit is hit. A call site cannot be half inlined, so the result is a heuristic rather than an optimum. The density order is used anyway, because it is the exact answer to the divisible version of the same question.

MediaBit allocation in a video encoder

An encoder must fit a frame inside a bitrate budget while picking a quality setting per block, so it ranks the options by quality gained per bit spent. Rate-distortion encoders do this with a multiplier lambda: every option whose quality per bit beats lambda is taken, and lambda is tuned until the budget is exactly full. That threshold is the ratio of the item the greedy fill would have cut, which is what makes the break item's density the price of one unit of capacity.

Why it works this way

Why per kilogram, and not simply most valuable first?

Value alone says nothing about what the space costs. With capacity 50 and items 10 kg worth 60, 20 kg worth 100 and 30 kg worth 120, most valuable first packs the 30 and the 20 for 220, while the density order packs the 10, the 20 and two thirds of the 30 for 240. Lightest first is the mirror mistake: it ignores value entirely. Only the ratio compares what you gain against what you spend, which is the quantity the swap argument needs.

For 0/1 the same order can be arbitrarily bad

Capacity 10, one item of 6 kg worth 12, and two items of 5 kg worth 9 each. Density order takes the 6 kg item first at 2.0 per kg, then nothing else fits, for a total of 12; the two 5 kg items would have given 18. Stretch the numbers and the gap widens without limit, so this is not a near miss you can accept. What survives into the 0/1 world is the fractional answer itself: it is never below the integer optimum, so solvers keep it as an upper bound. The packing greedy actually produces is a lower bound, and as the numbers above show, a bad one.

Comparing ratios: integer division and weightless items

Writing values[i] / weights[i] in an integer type silently floors, so 60/10 and 69/10 both become 6 and the sort settles the order by accident. Compare cross products instead, v1 * w2 against v2 * w1, and the ordering is exact with no floating point involved. An item of weight zero has no finite ratio. The cross product form happens to rank it ahead of everything, which is the right answer since it costs no room, while an integer divide throws instead. Take the zero weight items up front and sort the rest, and neither form can surprise you.

The sort is convenience, not necessity

Sorting is the only reason this costs O(n log n); the algorithm itself only needs the break item, the ratio at which the bag runs out of room. That is a weighted median, and linear-time selection finds it in O(n): partition around a candidate ratio, total the weight on the denser side, and recurse into whichever side the capacity falls in. The sorted version is the one to memorise, but the linear one is worth knowing exists.

Read more

Next up