Fractional Knapsack Problem — Greedy Approach

Fractional knapsack is where most engineers first encounter the concept of greedy correctness — the proof that taking the highest value-density item first is provably optimal, not just intuitively reasonable. The exchange argument used here is a template that appears throughout algorithm design: assume the greedy choice is not in an optimal solution, then show you can swap it in without making things worse.

In practice, fractional knapsack models continuous resource allocation: bandwidth allocation across network flows, portfolio optimisation with divisible assets, CPU time sharing. The 0/1 version (items must be whole) requires dynamic programming and is a completely different beast — knowing which version you're facing is the first question to ask.

The Greedy Strategy

Sort all items by value/weight ratio in descending order. Take items greedily — full items when they fit, a fraction of the next item when the bag is almost full.

def fractional_knapsack(capacity: float, weights: list, values: list) -> float:
    n = len(weights)
    # Create (value_density, weight, value) tuples
    items = sorted(zip(values, weights), key=lambda x: x[0]/x[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:
            # Take fraction
            total_value += value * (remaining / weight)
            remaining = 0
    return total_value

weights = [10, 20, 30]
values  = [60, 100, 120]
print(fractional_knapsack(50, weights, values))  # 240.0

Why Greedy Works Here But Not for 0/1 Knapsack

The greedy approach works for fractional knapsack because of the greedy choice property: taking the highest value-density item first is always locally and globally optimal — you can always 'undo' a partial choice by trading a fraction.

For 0/1 knapsack, taking the highest density item might leave a gap that no remaining item can fill optimally. Example: - Capacity = 10 - Item A: weight=6, value=10 (density 1.67) - Item B: weight=5, value=8 (density 1.60) - Item C: weight=5, value=8 (density 1.60)

Greedy picks A (density 1.67) then can only fit one of B/C — total = 10+8 = 18. Optimal picks B+C — total = 8+8 = 16. Wait — greedy wins here. But with capacity=10, items [{w=6,v=6},{w=5,v=5},{w=5,v=5}]: greedy picks first (density 1), then one of the others = 11. Optimal: pick both w=5 items = 10. Greedy wins again for fractional.

The key: with fractional items, the exchange argument holds perfectly — you can always swap parts of lower-density items for parts of higher-density ones to improve value.

Complexity

Sorting: O(n log n) Selection: O(n) Total: O(n log n) time, O(1) extra space

Compare with 0/1 knapsack: O(nW) dynamic programming.

Frequently Asked Questions