1. One-Liner
Fractional knapsack sorts items by value/weight ratio and greedily takes from the best ratio until capacity is full—allowing fractions of items.
2. The Problem It Solves
Capacity W, items with (value, weight). You may take any fraction of an item. Maximize total value carried.
3. The Core Idea
If you can slice pizza, you eat the tastiest per gram first. Ratios capture “bang per buck”; the greedy order is optimal by a exchange argument.
4. How It Works (Step-by-Step)
| Step | What Happens |
|---|---|
| 1. Ratio | Compute v/w for each item |
| 2. Sort | Descending by ratio |
| 3. Take | From each item, take min(remaining weight, left capacity) |
| 4. Stop | When capacity hits 0 |
5. Dry Run Example
W=50, items (60,10), (100,20), (120,30) → ratios 6,5,4. Take all of first two (30 wt), then 20/30 of third → value 60+100+80=240.
6. Key Properties
| Property | Value |
|---|---|
| Greedy optimal | Yes (fractional) |
| 0/1 knapsack | Not greedy—needs DP |
7. Where It Is Used
| Domain | Use |
|---|---|
| OR / logistics | Blending, continuous resources |
| Teaching | Contrast with 0/1 knapsack |
8. Interview Tips
Emphasize difference from 0/1; prove greedy with sort by ratio; watch floating point vs rational compares.
9. Comparison with Other Approaches
| Variant | Optimal algo |
|---|---|
| Fractional | Greedy O(n log n) |
| 0/1 | DP pseudo-polynomial |
10. Complexity
| Metric | Value |
|---|---|
| Time | O(n log n) sort + O(n) scan |
| Space | O(n) or O(1) if indices sorted |
Implementation Example (PYTHON)
def fractional_knapsack(values, weights, capacity):
items = sorted(zip(values, weights), key=lambda x: x[0] / x[1], reverse=True)
total = 0.0
for v, w in items:
if capacity <= 0:
break
take = min(w, capacity)
total += take * (v / w)
capacity -= take
return total