Same setup as 0/1 Knapsack: a set of items, each with its own weight and value, and a knapsack that can carry at most a fixed total weight. The one rule that changes is the one that matters most — items can now be split. Take 0.6 of a stove and get 0.6 of its value, no different from pouring out 60% of a bag of rice. That single relaxation turns an NP-hard problem into one solved by a single greedy pass: rank every item by value-per-weight, then take as much of the best-ratio item as fits, then the next-best, and so on until the knapsack is full or the items run out. This is the site's third Greedy entry, after Huffman Coding and Activity Selection — and the one with the sharpest before/after: 0/1 Knapsack's own Pitfalls section shows this exact ratio-greedy rule producing a real, checked wrong answer the moment items can't be split. This page reuses that page's exact five-item dataset to show the same rule succeeding once they can.
The same five items and capacity 10 as 0/1
Knapsack, not user-editable, same fixed-content convention this site's other DP/greedy demos use.
Press Step or Run to rank the items by value-per-weight and fill the
knapsack one item at a time, best ratio first — a solid green chip means fully taken, a striped chip
means partially taken (the fraction is shown), and a faded chip means there was no capacity left by the
time that item came up.
capacity filled: 0 / 10
Rank every item by value / weight and suppose, for contradiction, that some optimal
solution doesn't take items in that order — it leaves some capacity of the higher-ratio item
i untaken while taking a positive amount of a strictly lower-ratio item j.
Transfer a small amount of weight ε from j to i: total
weight used is unchanged, so the solution is still feasible, but the value changes by
ε · (ratioi − ratioj), strictly positive since
ratioi > ratioj. That contradicts optimality — so no optimal
solution can behave that way, and taking items in strictly-decreasing ratio order, each one filled
completely before moving to the next, is forced. Filling capacity is itself forced too: leaving room
unused while any item remains untaken can only be improved by taking more of it. The greedy algorithm
does exactly this, so it's not just a correct answer, it's compelled to be, in a way 0/1
Knapsack's own greedy heuristic can never be argued into — the swap in this proof depends entirely on
being able to move an arbitrarily small ε, which doesn't exist once items are
indivisible.
On the shared five-item dataset (capacity 10): ranked by ratio, Stove
(8/3 ≈ 2.67) comes first, then Food (9/4 = 2.25), then Tent
(13/6 ≈ 2.17), then Rope and Water tied at exactly 2. Taking Stove and
Food whole uses 7 of the 10 capacity for 17 value, leaving
3 — exactly half of Tent's weight — so the algorithm takes half of Tent
(6.5 value) and stops, with Rope and Water never reached. Total: 23.5,
strictly better than 0/1 Knapsack's own optimal 22 on the identical items and capacity,
which is expected, not a coincidence: every 0/1 solution is a valid fractional solution (every fraction
is 0 or 1), so the fractional optimum can never be lower, and is strictly higher exactly when the best
achievable 0/1 packing has to leave some capacity fragmented and unusable — precisely what happens
here, where the last usable slice of capacity is 3 units of a 6-unit tent that 0/1 Knapsack has to
either take whole (fits, at weight 6) or leave whole.
function fractionalKnapsack(items, capacity) {
const ranked = [...items].sort((a, b) => (b.value / b.weight) - (a.value / a.weight));
let remaining = capacity;
let totalValue = 0;
const taken = [];
for (const item of ranked) {
if (remaining <= 0) break;
const fraction = Math.min(1, remaining / item.weight);
totalValue += fraction * item.value;
remaining -= fraction * item.weight;
taken.push({ ...item, fraction });
}
return { totalValue, taken };
}This is the one demonstrated example where the greedy rule genuinely depends on the problem
being fractional, not just convenient for it. Feed the identical ranked order into 0/1
Knapsack's own indivisible rule and it takes Stove, Food, then Rope — the next item that still fits
whole after Stove and Food (weight 9, value 21) — because Tent's whole weight
6 no longer fits in the 3 remaining, and there's no way to take part of it.
That's a real, checked wrong answer for 0/1 Knapsack, worse than its own DP table's optimal
22; see 0/1 Knapsack's own Pitfalls for
that exact failure on this exact data. Nothing about the ranking changed between the two pages — only
whether the algorithm is allowed to stop partway through an item.
Ratio ties change which item gets credited, never the total value. Rope and Water
tie at exactly value/weight = 2 on this page's dataset, though neither is reached before
capacity runs out here. Checked on a smaller hand-built pair instead — item A (weight 4,
value 8) and item B (weight 6, value 12), both ratio
2, capacity 5 — taking A before B or B before A both land on total value
10. That's not a coincidence specific to this pair: once every item actually used shares
the same ratio, total value is just ratio × capacity used, independent of which
tied item contributed which unit. This is the opposite of 0/1 Knapsack's own tie caveat, where its
Pitfalls section shows the tie-break rule changing which set of items the demo reports even
though the value stays fixed — here, ties don't even change the value.
The greedy answer only stays optimal if "value" really is linear in the amount taken. Half a tent being worth exactly half the tent's value is the assumption that makes the exchange argument above go through — true for something like rice or fuel, false for anything with a per-unit fixed cost or a use-it-or-lose-it threshold (half of a working circuit board usually isn't worth half as much as a whole one). Real fractional-knapsack-shaped problems — splitting a divisible commodity like grain or a continuous resource like bandwidth across competing uses — tend to satisfy this; problems that look superficially similar but bundle indivisible value into the whole item belong back with 0/1 Knapsack instead, no matter how divisible the item is physically.
Time: O(n log n), entirely the cost of sorting by ratio — the fill
pass after that is a single O(n) walk down the sorted list, at most one item split.
Space: O(n) for the sorted copy. No table, no backtracking, no
exponential worst case anywhere — a direct consequence of the proof above rather than a coincidence:
once an optimal solution is forced into one specific shape (strictly-decreasing ratio order, greedily
filled), there's nothing left to search.
See Choosing a Greedy Strategy for how this entry's proof compares against the site's other nine Greedy entries — short version: this is Tier 1, exact on every input, by an ε-transfer argument that depends entirely on divisibility, which is exactly what 0/1 Knapsack lacks.