Fractional Knapsack — When Greedy Fails on 0/1 Constraints

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.

Proof of Optimality — Exchange Argument Formalised

The exchange argument is the formal proof that greedy is optimal. We'll walk through it step by step for fractional knapsack.

Let the items be sorted by value/weight ratio: v1/w1 >= v2/w2 >= ... >= vn/wn. Let G be the greedy solution. Let O be an optimal solution that differs from G at the first index i where they take different fractions.

Since G takes the maximum possible amount of item i, O takes less (or zero) of item i. O must compensate with some later item j (j > i) that has lower density. Replace a unit weight of item j with a unit weight of item i in O. The value of O increases (or stays same) because vi/wi >= vj/wj. If it stays same, density ties don't matter.

Thus we can transform O into G without decreasing value, proving G is optimal.

This argument is the foundation for greedy optimality proofs in many other problems: activity selection, Huffman coding, coin change (canonical systems).

Complexity and Space Considerations

Sorting: O(n log n) — dominated by sort. Selection pass: O(n) — one scan. Total time: O(n log n). Space: O(1) extra (if sorting in place), otherwise O(n) for a copy.

Compare with 0/1 knapsack dynamic programming: O(nW) time and O(W) space (with 1D array). For large W, fractional knapsack's O(n log n) is much faster.

Trick: If weights are small integers (W <= n log n), you can use counting sort for O(n + W) time, but in practice the built-in sort is fine.

Real-World Applications and Variations

Fractional knapsack appears in many continuous resource allocation problems: - Bandwidth allocation: Splitting bandwidth among flows proportionally to their 'value' (e.g., priority * throughput). - CPU time scheduling: Weighted fair queuing (WFQ) uses a similar greedy approach — allocate CPU to the highest 'density' process first. - Portfolio optimisation: When assets are perfectly divisible (e.g., stocks in large markets), the greedy by expected return per unit risk gives the optimal mix. - Mixing raw materials: In manufacturing, you have limited capacity and want to maximise profit by blending ingredients of different value densities.

Variations: - Bounded fractional knapsack: Each item has a maximum fraction you can take (e.g., you cannot take more than 50% of a shared resource). Still solvable by greedy after adjusting densities? Not necessarily — requires a more complex approach. - Multiple knapsacks: Have several bags. Greedy still works? Not in general — becomes a variant of bin packing. - Knapsack with penalties: Taking a fraction incurs overhead (e.g., setup time per item). Breaks the greedy property.

Common Mistakes and Edge Cases

Even for a simple greedy algorithm, several mistakes slip into code:

1. Sorting by value only: Forgetting to divide by weight. Takes expensive heavy items first, not the best value per unit weight.
2. Integer division: In languages like C++ or Java, dividing two integers gives an integer, messing up density order. Use double or compare cross-multiplication.
3. Floating point equality: When two densities are equal, stable sort matters for reproducibility but not optimality.
4. Off-by-one in capacity check: Taking a fraction when the item fits exactly but you compare weight < remaining instead of <=.
5. Not handling zero-weight items: Division by zero if weight = 0. Check if weight > 0 before dividing.
6. Assuming capacity is integer: If capacity is integer but weights are floats, capacity comparison can drift.

Comparison with 0/1 Knapsack

Understanding when to use each is critical. Here's a direct comparison:

• Fractional Knapsack: Items divisible, greedy gives optimal solution, O(n log n).
• 0/1 Knapsack: Items indivisible, DP required, O(nW) time.
• Unbounded Knapsack: Items can be taken multiple times, DP also used but with different recurrence.

The fundamental difference is the fraction. In fractional, the exchange argument works because you can always swap a small piece of a low-density item for an equal piece of a high-density one. In 0/1, you can't swap a piece — you must swap whole items, which may not fit in the remaining space.

Frequently Asked Questions