Greedy Algorithms5 min read

Fractional Knapsack

Filling a backpack with gold dust — take the most valuable per gram first
time:Fast · \(O(n \log n)\)space:Minimal · \(O(1)\)works because:Items are divisible — no wasted capacity

Imagine you're a prospector with a backpack that holds exactly 10 kg. You've found piles of gold dust, silver powder, and copper flakes. You can scoop up any amount from any pile — even a half-scoop. Which piles do you scoop first?

Easy: calculate the value per gram of each material, then scoop the most valuable one until it's gone (or your pack is full), then move to the next. Because you can take fractions, you never leave capacity wasted.

That's the fractional knapsack problem, and greedy solves it optimally in \(O(n \log n)\).

The Algorithm

1. For each item, compute its value-to-weight ratio: v_i / w_i.
2. Sort items by ratio in descending order.
3. Greedily fill your pack: take each item completely if it fits; if not, take as much of it as fills the remaining space exactly. Stop when the pack is full.

Why This Is Correct

Every gram of capacity should earn you as much value as possible. If you ever have a gram devoted to a lower-ratio item when a higher-ratio item is still available, you could swap that gram and earn more. The exchange argument: replace any unit of lower-ratio material with the same unit of higher-ratio material — value strictly increases. Therefore, there's no benefit to deviating from the highest-ratio order.

The Critical Contrast: 0/1 Knapsack

Now imagine the same problem, but each material comes as a solid ingot — you must take the whole thing or nothing. This is 0/1 Knapsack, and greedy fails here.

Example: backpack holds 10 kg. Items: A (6 kg, $12, ratio 2.0), B (5 kg, $10, ratio 2.0), C (4 kg, $8, ratio 2.0). Greedy (by ratio, break ties arbitrarily) might pick A first (6 kg, $12), then B doesn't fit (6+5=11>10), so take C (6+4=10, total $20). But B+C together = 5+4 = 9 kg, $18 — worse. Actually here greedy works. Try: W=10, A=(6,10), B=(5,9), C=(5,9). Ratios: 1.67, 1.8, 1.8. Greedy picks B+C? No — with exact tie-breaking it might pick A first ($10, 6kg used, 4kg left), then neither B nor C fits. Total: $10. But B+C = $18. Greedy is beaten by $8.

The moment items are indivisible, the greedy choice property breaks. You need 2D Dynamic Programming instead: dp[i][w] = max value using first i items with capacity w.

Note: Fractions are the superpower here. The last gram in your backpack can always be filled with exactly the right amount of the best remaining material. That perfect fill-ability is what makes the greedy choice property hold.

Fractional Knapsack — Greedy by Value/Weight Ratio

def fractional_knapsack(capacity, items):
    # items: list of (weight, value)
    # sort by value/weight ratio descending
    items_sorted = sorted(items, key=lambda x: x[1]/x[0], reverse=True)
    total_value = 0.0
    remaining = capacity
    for weight, value in items_sorted:
        if remaining <= 0:
            break
        take = min(weight, remaining)
        total_value += take * (value / weight)
        remaining -= take
    return total_value


# Items: (weight, value)
items = [(10, 60), (20, 100), (30, 120)]
capacity = 50
result = fractional_knapsack(capacity, items)
print(f"Max value: {result:.1f}")
# Take all of item 3 (30kg, $120), all of item 2 (20kg, $100),
# total weight 50kg. Value = 240.
Output
Max value: 240.0

Complexity

⚖️ Compute & sort by ratioDominant cost — ratios take \(O(n)\), sort takes \(O(n \log n)\)
One-time sort\(O(n \log n)\)
🎒 Greedy fill scanWalk items in ratio order, fill until capacity is gone
Single pass\(O(n)\)
📦 SpaceTrack only remaining capacity and running total value
Constant\(O(1)\)
🧱 0/1 Knapsack (comparison)Indivisible items break greedy — needs 2D DP table
Pseudo-polynomial\(O(n · W)\)

Quick check

Items: A (weight 4, value 20), B (weight 3, value 18), C (weight 6, value 24). Backpack holds 8 kg. What's the max value?

Continue reading

Greedy Pattern
Always grab the biggest slice of pizza — sometimes that's optimal, sometimes it isn't
→
0/1 Knapsack
Pack a suitcase for maximum value — each item is all-or-nothing
→
Interval Scheduling
Book as many non-overlapping meetings as possible — always pick the one that ends earliest
→