Fractional knapsack
mediumBecause items can be split, there is never a reason to leave a denser item partly untaken. Forbid splitting and the same algorithm becomes wrong - which is exactly why 0/1 knapsack needs DP.
O(n log n)Space O(1)Saved in this browser - no sign-up, nothing sent anywhere.
How fractional knapsack works
Sort by value per unit of weight and pour the densest material in first. With values 60, 100, 120, 40, 90 and weights 10, 20, 30, 15, 25, the densities run 6.0, 5.0, 4.0, 2.7, 3.6 - so the order is fixed before the bag is touched. Every unit of capacity should hold the most valuable material still available, and because items can be split, nothing ever blocks that.
The proof is a one-line exchange. Suppose an optimal load carries some material of density 3.6 while denser 5.0 material sits partly untaken. Swap one unit of the former for one unit of the latter: the weight is unchanged and the value strictly rises, contradicting optimality. Fractions are what make the swap always available - no unit of capacity is ever committed to a whole item.
Forbid splitting and the same sort becomes wrong. On this module's default input, density order under the 0/1 rule packs 60 + 100 + 40 = 200 into capacity 50, while the combination 100 + 120 makes 220. Leftover capacity that no remaining item fits is the failure mode, and it is exactly the gap dynamic programming exists to close for the 0/1 knapsack.
Step by step
- Capacity 50, five items. Compute densities: 60/10 is 6.0, 100/20 is 5.0, 120/30 is 4.0, 90/25 is 3.6, 40/15 is 2.7.
- Sort densest first: 6.0, 5.0, 4.0, 3.6, 2.7. The bag fills strictly in this order.
- The 6.0 item weighs 10 and fits whole. Take all of it: value 60, capacity 40 remaining.
- The 5.0 item weighs 20 and also fits whole. Value climbs to 160 with 20 capacity left.
- The 4.0 item weighs 30, but only 20 capacity remains. Take 20/30 - two thirds - of it for 80 more value.
- The bag is now exactly full: total value 240, one item split, nothing after it considered.
Complexity
| Worst case time | O(n log n) |
|---|---|
| Space | O(1) |
Sorting by value density; the greedy choice property holds only with fractions.
Reference implementation
Python
def fractional_knapsack(capacity, items):
"""items: list of (value, weight). Fractions are allowed."""
items.sort(key=lambda x: x[0] / x[1], reverse=True) # best density first
total = 0.0
for value, weight in items:
if weight <= capacity:
capacity -= weight
total += value
else:
total += value * (capacity / weight) # partial item
break
return totalJavaScript
function fractionalKnapsack(capacity, items) {
items.sort((a, b) => b.value / b.weight - a.value / a.weight);
let total = 0;
for (const { value, weight } of items) {
if (weight <= capacity) { capacity -= weight; total += value; }
else { total += value * (capacity / weight); break; }
}
return total;
}Worth noticing
Density is the right ordering, and fractions are why
Every unit of capacity should hold the most valuable material available. Because items can be split, there is never a reason to leave a denser item partly untaken in favour of a lighter one.
This is exactly where greedy stops working for 0/1
Forbid fractions and the same algorithm becomes wrong: you can be left with unusable leftover capacity that a different, less dense combination would have filled. That gap is why the 0/1 knapsack needs dynamic programming.
The last item is usually partial
The greedy run fills the bag exactly, with at most one item split. That single fractional item is the difference between an O(n log n) sort and an O(n·W) table.
Common pitfalls
- Reusing this greedy for 0/1 knapsack. On this exact input, density order without splitting packs 200 while 100 + 120 makes 220 - the classic wrong answer.
- Sorting by raw value. Taking the 120 item then the 100 fills the bag for 220, twenty short of the 240 that density order reaches.
- Skipping the fractional step. Stopping at whole items strands capacity and value; the split of the final item is precisely where this greedy earns the optimum.
- Computing the fraction with integer division. remaining/item.weight must stay floating point, or the partial item silently contributes zero value.
- Not asking whether items can be split. That single question decides between this O(n log n) sort and the O(n·W) dynamic programming table.
Where it is used
- Allocating divisible resources - bandwidth, budget, fuel - across options priced per unit.
- The upper bound inside branch-and-bound solvers for 0/1 knapsack: the fractional optimum bounds every subtree.
- Loading bulk cargo like grain or liquids, where fractions are physically real.
- An interview screen for whether you ask if items are divisible before committing to greedy or DP.
Frequently asked questions
What is the time and space complexity of fractional knapsack?
O(n log n) time and O(1) extra space. Sorting the items by value density is the entire cost; the fill loop runs once over the sorted list and stops at the first item that has to be split.
Why does greedy work for fractional knapsack but fail for 0/1?
Splitting means capacity is never stranded: the bag can always be topped up with the best remaining density. With whole items, a dense early pick can leave a hole nothing fits - 200 versus the possible 220 on this module's input - so the 0/1 version needs dynamic programming.
What happens when two items have the same density?
Any order between them yields the same total value, because each unit of capacity earns the same value either way. Ties can be broken arbitrarily; only the identity of the item that ends up split can change, never the optimum.
How much of the last item gets taken?
Remaining capacity divided by the item's weight. On the default input that is 20/30, so two thirds of the 120-value item contributes 80. At most one item is ever fractional - everything before it was taken whole, and everything after it is ignored.