Introduction
The fractional knapsack problem asks: given a set of items each with a weight and a value, and a knapsack with limited weight capacity, how do you choose (possibly partial) amounts of items to maximize total value? Because items can be split into fractions, this variant is solvable optimally by a simple greedy strategy, in contrast to the 0/1 knapsack problem where items must be taken whole and greedy fails.
Cricket analogy: Filling a limited number of overs with the highest run-scoring batting approach works if you can send a batsman for a partial over, but if you must commit a batsman to a whole over (0/1 style), greedy over-allocation can misfire.
Algorithm/Syntax
def fractional_knapsack(items, capacity):
"""
items: list of (value, weight) tuples
capacity: maximum total weight the knapsack can hold
returns (max_value, chosen) where chosen is a list of
(value, weight, fraction_taken)
"""
# Greedy criterion: value-to-weight ratio, highest first
ranked = sorted(items, key=lambda vw: vw[0] / vw[1], reverse=True)
total_value = 0.0
remaining = capacity
chosen = []
for value, weight in ranked:
if remaining <= 0:
break
take_weight = min(weight, remaining)
fraction = take_weight / weight
total_value += fraction * value
remaining -= take_weight
chosen.append((value, weight, fraction))
return total_value, chosen
Explanation
The greedy criterion is value density: value divided by weight (value/weight ratio). Sort items in descending order of this ratio, then greedily take as much as possible of the highest-density item, moving to the next item once the current one is exhausted or the knapsack is full. Because fractions are allowed, this always achieves the optimum: if any optimal solution takes less than the maximum possible of a higher-ratio item while taking more of a lower-ratio item, you can always shift weight from the lower-ratio item to the higher-ratio one and strictly increase (or at worst maintain) total value -- the exchange argument holds cleanly here specifically because fractional amounts make the swap always possible.
Cricket analogy: Ranking batsmen by strike-rate-per-ball-faced and sending in the highest-ratio hitter first, taking as many balls as the innings allows before moving to the next, always maximizes the total score because partial overs let you shift balls freely between batsmen.
This greedy ratio strategy does NOT work for the 0/1 knapsack problem, where each item must be taken entirely or not at all. There, the inability to take partial amounts breaks the exchange argument, and you need dynamic programming (see 0-1-knapsack-problem) to guarantee the true optimum.
Example
items = [(60, 10), (100, 20), (120, 30)] # (value, weight)
capacity = 50
total_value, chosen = fractional_knapsack(items, capacity)
print(total_value, chosen)
# Trace: ratios -> 60/10=6.0, 100/20=5.0, 120/30=4.0
# sorted (desc by ratio): (60,10) ratio 6.0, (100,20) ratio 5.0, (120,30) ratio 4.0
# Take (60,10) fully: remaining = 50-10 = 40, value += 60 -> total=60
# Take (100,20) fully: remaining = 40-20 = 20, value += 100 -> total=160
# Take (120,30) partially: fraction = 20/30 = 0.667, value += 0.667*120 = 80 -> total=240
# remaining = 0, loop ends
# Output: total_value = 240.0
# chosen = [(60,10,1.0), (100,20,1.0), (120,30,0.667)]
Complexity
Sorting n items by value/weight ratio costs O(n log n). The subsequent greedy fill is a single O(n) pass over the sorted items. Overall time complexity is O(n log n), with O(n) space for the sorted list and the chosen output. This is far cheaper than the pseudo-polynomial O(n * capacity) dynamic-programming approach required for 0/1 knapsack.
Cricket analogy: Sorting a squad of n players by strike rate takes O(n log n), then a single pass down the batting order to fill the innings takes O(n), far cheaper than the 0/1-style DP that would need to check every over-capacity combination.
Key Takeaways
- The greedy criterion is value-to-weight ratio (value density), sorted in descending order.
- Because items can be split, the exchange argument holds fully, guaranteeing greedy finds the global optimum.
- Fill the knapsack by taking as much as possible of the highest-ratio item first, then move down the ranked list.
- Runs in O(n log n) time, dominated by sorting -- much faster than the DP-based 0/1 knapsack solution.
- Contrast with 0/1 knapsack is the canonical example of when greedy applies versus when it fails.
Practice what you learned
1. What is the greedy criterion used to sort items in the fractional knapsack problem?
2. Why is the fractional knapsack problem solvable optimally by a greedy algorithm, unlike 0/1 knapsack?
3. What is the time complexity of the fractional knapsack greedy algorithm for n items?
4. In the fractional knapsack example with items (60,10), (100,20), (120,30) and capacity 50, what is the maximum achievable value?
Was this page helpful?
You May Also Like
The Greedy Algorithm Paradigm
Learn how greedy algorithms build solutions one locally optimal choice at a time, and when that strategy actually yields a global optimum.
0/1 Knapsack Problem
Learn the classic 0/1 knapsack DP formulation, its O(nW) recurrence, and how to reconstruct the chosen items.
Activity Selection Problem
Select the maximum number of non-overlapping activities from a schedule using a greedy earliest-finish-time strategy.
Introduction to Dynamic Programming
Learn what dynamic programming is and the two conditions — overlapping subproblems and optimal substructure — that make it applicable.