What is the Fractional Knapsack Problem?
Learn the fractional knapsack greedy algorithm: sort by value-to-weight ratio, fill capacity, and why it beats DP for divisible items.
Expected Interview Answer
The fractional knapsack problem asks you to fill a capacity-limited knapsack with items that can be broken into fractions, maximizing total value by always taking as much as possible of the item with the highest value-to-weight ratio first.
Because items can be split, the optimal strategy is purely greedy: compute each item’s value-to-weight ratio, sort items by that ratio in descending order, then take whole items in that order until the remaining capacity cannot fit a full item, at which point take only the fraction of the next item that fits. This works because taking a partial unit of the highest-ratio item always yields at least as much value per unit weight as taking any other item, so there is never a reason to prefer a lower-ratio item while capacity and higher-ratio items remain. This is the key contrast with the 0/1 knapsack, where items cannot be split and greedy-by-ratio can fail, forcing dynamic programming instead. The fractional version runs in O(n log n) for the sort, with the fill step itself being O(n).
- Greedy-by-ratio is provably optimal here (unlike 0/1 knapsack)
- O(n log n) time, no DP table required
- Simple to implement and reason about
- Models divisible-resource allocation cleanly
AI Mentor Explanation
A team has a limited number of training-ground hours left before a match and several drills, each giving a skill-improvement value per hour spent. Because drills can be practiced in partial time blocks, the coach ranks drills by improvement-per-hour and fills the schedule with the highest-ratio drill first, using it fully until either the drill runs out or the hours run out, then moves to the next-best ratio drill, splitting it if needed to use every remaining minute. This differs sharply from picking whole training camps that cannot be split, where greedy ranking alone would not guarantee the best use of limited hours. Filling by descending value-per-hour, allowing fractions, is exactly the fractional knapsack strategy.
Step-by-Step Explanation
Step 1
Compute value-to-weight ratios
For each item, calculate value divided by weight.
Step 2
Sort items by ratio descending
Items offering the most value per unit weight come first.
Step 3
Take whole items greedily
Add each item fully while its weight still fits in the remaining capacity.
Step 4
Take a fraction of the next item
When a full item no longer fits, take only the fraction of it needed to exactly fill remaining capacity, then stop.
What Interviewer Expects
- Explain why sorting by value-to-weight ratio is optimal for the fractional case
- Clearly contrast with 0/1 knapsack, where items cannot be split and greedy fails
- State the O(n log n) time complexity driven by the sort
- Walk through taking a partial fraction of the last item added
Common Mistakes
- Applying the same greedy-by-ratio approach to 0/1 knapsack, where it does not always work
- Sorting by value or weight alone instead of the ratio
- Forgetting to take a fraction of the final item instead of skipping it entirely
- Not handling capacity reaching exactly zero as a stopping condition
Best Answer (HR Friendly)
“The fractional knapsack problem is about filling a limited-capacity container with items that can be split into pieces, to maximize total value. I sort items by value per unit weight, take as much of the best one as fits, and if a full item does not fit anymore, take just the fraction of it that does — a pure greedy approach that is provably optimal because items are divisible.”
Code Example
def fractional_knapsack(items, capacity):
# items: list of (value, weight)
items = sorted(items, key=lambda it: it[0] / it[1], reverse=True)
total_value = 0.0
remaining = capacity
for value, weight in items:
if remaining <= 0:
break
if weight <= remaining:
total_value += value
remaining -= weight
else:
fraction = remaining / weight
total_value += value * fraction
remaining = 0
return total_valueFollow-up Questions
- Why does the greedy approach fail for the 0/1 knapsack problem?
- How would you adapt this if some items cannot be split at all while others can?
- What is the time complexity if items are already sorted by ratio?
- How would you solve 0/1 knapsack instead, and what is its time complexity?
MCQ Practice
1. What is the greedy criterion used to sort items in the fractional knapsack problem?
Sorting by value-to-weight ratio descending ensures the most efficient use of each unit of capacity first.
2. What happens when the next item in the sorted order does not fully fit the remaining capacity?
Because items are divisible, taking the exact fraction that fits maximizes value for the remaining capacity.
3. Why does greedy-by-ratio fail for the 0/1 knapsack problem but work for the fractional version?
Indivisibility in 0/1 knapsack means a locally optimal ratio choice can block a better combination, requiring dynamic programming instead.
Flash Cards
What is the greedy sort key for fractional knapsack? — Value-to-weight ratio, sorted descending.
What happens to the last item added if it does not fully fit? — Only the fraction that fits the remaining capacity is taken.
What is the time complexity of the fractional knapsack greedy algorithm? — O(n log n), dominated by sorting items by ratio.
Why does greedy-by-ratio work here but not for 0/1 knapsack? — Items are divisible, so there is no risk of a ratio-optimal item overshooting capacity and blocking a better combination.