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.

Fractional Knapsack — The Greedy Algorithm That Works Only When You Can Break Items

Fractional knapsack is a greedy algorithm that solves the problem of selecting items to maximize total value given a weight capacity, with the critical twist that you can take any fraction of an item. The algorithm sorts items by value-to-weight ratio (value/weight) in descending order, then iteratively takes as much as possible of the highest-ratio item until the knapsack is full. This yields an optimal solution in O(n log n) time due to the sort, and O(n) for the selection phase.

The key property that makes greedy optimal here is the ability to take fractions — the problem exhibits the greedy-choice property and optimal substructure. Because you can always fill the remaining capacity with a fraction of the next best item, there is no need to backtrack or reconsider earlier choices. This contrasts sharply with the 0/1 knapsack problem, where greedy fails because you cannot take a fraction of an item, and the optimal solution may require skipping a high-ratio item to make room for a combination of lower-ratio items.

Use fractional knapsack when you have divisible resources — for example, allocating bandwidth to traffic classes, distributing CPU time among processes, or blending raw materials where partial lots are acceptable. It is a textbook example of when greedy works perfectly, but it is also a trap: engineers often apply the same greedy logic to 0/1 knapsack problems (e.g., selecting which servers to upgrade under a budget) and get suboptimal results. The difference is whether you can take a fraction — if not, greedy is not safe.

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.

Why Naive Heuristics Fail — Two Concrete Deployments

Before you cargo-cult the value/weight ratio, let’s see why picking by weight or value alone will get you fired. Two quick examples.

Case 1: Lightest-first. Items: value [10, 10, 10, 100], weight [10, 10, 10, 30], capacity 30. Lightest-first grabs three 10-weight items for value 30. Optimal? Take the single 30-weight item — value 100. You just left 70 on the table because you didn’t check density.

Case 2: Highest-value-first. Items: value [10, 10, 10, 20], weight [10, 10, 10, 30], capacity 30. Greedy picks the 20-value item (weight 30) for total 20. Alternative: three 10-weight items give 30 value. You lost 33% because one fat high-value item starved the rest.

Both heuristics fail because they ignore the ratio of value to weight. That ratio is your compass in fractional knapsack. Memorise it: value per unit weight is the only signal that matters here.

// io.thecodeforge — dsa tutorial

public class NaiveHeuristics {
    public static void main(String[] args) {
        int[] values  = {10, 10, 10, 100};
        int[] weights = {10, 10, 10, 30};
        int capacity = 30;
        
        // Lightest-first: take three weight-10 items
        double lightestFirst = 10 + 10 + 10;
        System.out.println("Lightest-first total: " + lightestFirst);
        
        // Optimal: take single weight-30 item
        double optimal = 100;
        System.out.println("Optimal total: " + optimal);
    }
}

The Ratio Sort Algorithm — O(n log n) Time, O(n) Space

Here’s the one algorithm you need. Steps: 1. Calculate value/weight ratio for each item. 2. Sort items by ratio descending. 3. Walk the sorted list. Take full items until capacity doesn’t allow it, then take a fraction of the next item.

That’s it. The greedy choice works because the problem allows breaking items — you’re not forced to commit to a whole item. The ratio tells you the marginal gain per unit weight. You want the highest marginal gain first.

Complexity: sorting dominates at O(n log n). Space is O(n) for the item array (or O(1) if you sort in-place). This is optimal for fractional knapsack — you can’t beat a comparison-based sort for general inputs.

Edge case: if ratios tie, break ties arbitrarily. The proof doesn’t depend on tie-breaking order. Just don’t let ties paralyse you.

// io.thecodeforge — dsa tutorial

import java.util.*;

class Item implements Comparable<Item> {
    int value, weight;
    Item(int v, int w) { value = v; weight = w; }
    public int compareTo(Item other) {
        double r1 = (double) value / weight;
        double r2 = (double) other.value / other.weight;
        return Double.compare(r2, r1); // descending
    }
}

public class FractionalKnapsackGreedy {
    static double maxValue(int[] values, int[] weights, int capacity) {
        int n = values.length;
        Item[] items = new Item[n];
        for (int i = 0; i < n; i++)
            items[i] = new Item(values[i], weights[i]);
        Arrays.sort(items);
        
        double totalValue = 0;
        for (Item item : items) {
            if (capacity >= item.weight) {
                capacity -= item.weight;
                totalValue += item.value;
            } else {
                totalValue += (double) capacity / item.weight * item.value;
                break;
            }
        }
        return totalValue;
    }

    public static void main(String[] args) {
        int[] values  = {60, 100, 120};
        int[] weights = {10, 20, 30};
        int capacity = 50;
        System.out.println(maxValue(values, weights, capacity));
    }
}

Analysis — Why Ratio Sort Gives Correct Fractional Fill

Greedy correctness for fractional knapsack rests on a single insight: the marginal value per unit weight is constant for each item. Sorting by value/weight ratio ensures that when we fill the knapsack, we always take the item with the highest remaining marginal gain. The exchange argument formalises this: any optimal solution that does not take the highest-ratio item first can be transformed by swapping a lower-ratio portion with an equal weight of the highest-ratio item, increasing total value without changing weight. Because we can break items, this swap never leaves partial items stranded — we always replace a lower-density fragment with a higher-density one. The proof terminates when the knapsack is full and every selected fragment has ratio ≥ any unselected fragment. No tie-breaking issues arise because fractional allocation absorbs differences. Complexity is dominated by sorting O(n log n); after sorting, a single linear pass fills the knapsack in O(n) time. Space is O(1) beyond input storage. The analysis confirms that the greedy schedule yields global optimum only because the problem’s continuous nature admits marginal reasoning.

// io.thecodeforge — dsa tutorial

import java.util.Arrays;

public class FractionalKnapsack {
    static class Item { int value, weight; double ratio; }
    
    static double maxValue(int capacity, Item[] items) {
        Arrays.sort(items, (a,b) -> Double.compare(b.ratio, a.ratio));
        double totalValue = 0;
        for (Item item : items) {
            if (capacity == 0) break;
            double take = Math.min(item.weight, capacity);
            totalValue += take * item.ratio;
            capacity -= take;
        }
        return totalValue;
    }
}

Implementation — Clean, Minimal, Production-Ready Code

Implementation follows directly from analysis: define an Item class with value, weight, and computed ratio. Sorting uses Java’s built-in comparator on ratio descending. The main loop iterates sorted items, taking min(remaining capacity, item weight) and decreasing capacity. No recursion, no extra data structures. Edge cases handled naturally: if an item weight exceeds capacity, we take a fraction; if capacity runs out early, the loop breaks. Input validation (non-negative weights, positive capacity) is left to the caller — the algorithm assumes valid numeric data. This implementation runs in O(n log n) time, O(1) extra space, and is safe for up to several million items (heap sort memory permitting). Production code would bundle the logic into a utility class with static method taking arrays of primitive doubles for speed. The example below shows a complete, testable version that prints the maximum value for a known test case. Note the ratio is not stored — we compute it on the fly during comparison to avoid duplicating data. This reduces memory footprint for large inventory lists.

// io.thecodeforge — dsa tutorial

import java.util.*;

public class FractionalKnapsackComplete {
    public static void main(String[] args) {
        int[] value = {60, 100, 120};
        int[] weight = {10, 20, 30};
        int capacity = 50;
        System.out.println(maxValue(value, weight, capacity));
    }

    static double maxValue(int[] values, int[] weights, int capacity) {
        int n = values.length;
        Integer[] indices = new Integer[n];
        for (int i = 0; i < n; i++) indices[i] = i;
        Arrays.sort(indices, (i, j) -> Double.compare(
            (double)values[j] / weights[j],
            (double)values[i] / weights[i]));
        double total = 0;
        for (int idx : indices) {
            if (capacity == 0) break;
            double take = Math.min(weights[idx], capacity);
            total += take * (double)values[idx] / weights[idx];
            capacity -= take;
        }
        return total;
    }
}

Output — What the Algorithm Actually Produces

The fractional knapsack greedy algorithm outputs a single value: the maximum total value achievable by taking fractions of items up to the knapsack's weight capacity. Unlike 0/1 knapsack, the output is always optimal and can include partial items. For a knapsack of capacity W and n items sorted by value/weight ratio, the output is the sum of values from whole items taken in descending ratio order plus the fractional value of the first partially taken item. Example: items (value 100, weight 20), (value 120, weight 30), capacity 50. Ratios: 5.0, 4.0. Take full item 1 (weight 20, value 100), then 30/30 of item 2 (value 120), total output = 100 + 120 = 220. If capacity were 40, take full item 1 (20 weight, 100 value), then 20/30 of item 2 (value 80 → 120 * (20/30)), output = 180. The output is a double; the algorithm never returns which fractions to take, only the maximum value. In production systems, the fractional amount per item can also be tracked if needed, but the core output is just the scalar total.

// io.thecodeforge — dsa tutorial
import java.util.*;
public class FractionalKnapsack {
    public static double maxValue(int[] val, int[] wt, int cap) {
        int n = val.length;
        Item[] items = new Item[n];
        for (int i = 0; i < n; i++)
            items[i] = new Item(val[i], wt[i]);
        Arrays.sort(items, (a,b) -> Double.compare(b.ratio, a.ratio));
        double totalValue = 0.0;
        for (Item item : items) {
            if (cap <= 0) break;
            if (item.weight <= cap) {
                totalValue += item.value;
                cap -= item.weight;
            } else {
                totalValue += item.value * ((double) cap / item.weight);
                cap = 0;
            }
        }
        return totalValue;
    }
    static class Item {
        int value, weight; double ratio;
        Item(int v, int w) { this.value=v; this.weight=w; this.ratio=(double)v/w; }
    }
}