Fractional Knapsack: The Greedy Algorithm That Actually Works

1. Problem and Motivation

Suppose you manage a cargo truck with a fixed weight capacity. A warehouse offers you several lots of goods, each with a total weight and a total sale value. In the classic 0/1 Knapsack Problem, each lot must be taken whole or left behind entirely — you cannot load "part of a lot." But some goods really are divisible: grain, crude oil, cash, network bandwidth, CPU time. If the goods can be split into any fraction, and value scales proportionally with the amount taken, you are solving the Fractional Knapsack Problem: given $n$ items with weights $w_1,\dots,w_n$ and values $v_1,\dots,v_n$, and a capacity $W$, choose an amount $x_i \in [0, w_i]$ of each item to load so that $\sum_i x_i \le W$ and the total value $\sum_i \frac{v_i}{w_i}x_i$ is maximized.

The single-word difference — "fractional" instead of "0/1" — changes everything about how the problem is solved. 0/1 Knapsack has no known polynomial-time exact algorithm in general (it is NP-hard) and is normally solved with dynamic programming in pseudo-polynomial time. Fractional Knapsack, by contrast, is solved optimally by one sorting pass and one greedy scan — no table, no recursion, no subset enumeration. This lesson builds that greedy algorithm from first principles and proves, rather than merely asserts, why it is safe.

2. Prerequisites

This lesson assumes comfort with arrays, sorting, big-O notation, and basic proof by contradiction. It is strongly recommended that you have already read the Knapsack section of Part 15: Core DP Patterns, which covers the 0/1 Knapsack Problem solved by dynamic programming. That page states plainly: "0/1 means each item is either taken or left — no fractions." Keep that sentence in mind; it is the entire reason the two problems are solved by completely different techniques, and we will return to it directly in the Correctness and Complexity sections below. We will not repeat the 0/1 DP derivation here — only contrast against it.

3. Terminology

• Value-to-weight ratio: $r_i = v_i / w_i$, the value returned per unit of capacity consumed by item $i$. This is the single number the greedy algorithm ranks items by.
• Fractional selection: the amount taken of item $i$ is $x_i \in [0, w_i]$, or equivalently a fraction $f_i = x_i / w_i \in [0,1]$. Contrast with 0/1 Knapsack, where $x_i \in \{0, w_i\}$ only — no value strictly between.
• Feasible allocation: a choice of $x_1,\dots,x_n$ such that $\sum_i x_i \le W$.
• Greedy order: the sequence of items visited, sorted by strictly decreasing $r_i$.
• Saturated item: an item taken at its full weight, $x_i = w_i$.

4. A Concrete Example

5. Brute Force and Its Limit

For 0/1 Knapsack, "brute force" means trying every subset of items, and dynamic programming tames that by building a table over $(\text{item index}, \text{remaining capacity})$ states. Fractional Knapsack cannot use that same DP table at all: the fraction $x_i$ taken of an item is a continuous value in $[0, w_i]$, not a discrete choice, so there is no finite table of states to fill in — "try every combination of fractions" is not even a countable brute force, let alone a practical one.

A more honest brute force for this problem is: try every possible ordering of the $n$ items, and for each ordering greedily fill the knapsack in that order, then keep the best result across all $n!$ orderings. This is correct but wasteful, and once you see the core insight below you can prove that only one ordering ever needs to be tried — decreasing ratio order — so the $n!$ search collapses to a single $O(n \log n)$ sort. The naive method is not wrong, it is simply solving a search problem that the structure of the problem has already answered in advance.

6. Plain-English Steps and Pseudocode

1. Compute the ratio $r_i = v_i / w_i$ for every item.
2. Sort the items by decreasing $r_i$.
3. Initialize remaining capacity to $W$ and total value to 0.
4. For each item in sorted order: if its full weight fits in the remaining capacity, take it fully and subtract its weight from the remaining capacity; otherwise take exactly the fraction that exhausts the remaining capacity, add its fractional value, and stop.
5. Return the accumulated total value (and, if needed, the fraction taken of each item).

fractionalKnapsack(items, W):
    sort items by decreasing value/weight ratio
    remaining = W
    totalValue = 0
    for item in items:
        if remaining <= 0:
            break
        if item.weight <= remaining:
            totalValue += item.value
            remaining -= item.weight
        else:
            fraction = remaining / item.weight
            totalValue += fraction * item.value
            remaining = 0
    return totalValue

flowchart TD
    A["Start: items with weight and value, capacity W"] --> B["Compute ratio r_i = v_i / w_i for each item"]
    B --> C["Sort items by ratio, decreasing"]
    C --> D["Take next item in sorted order"]
    D --> E{"Does the full item fit in remaining capacity?"}
    E -->|"Yes: weight <= remaining"| F["Take it fully
value += v_i, remaining -= w_i"]
    E -->|"No: weight > remaining"| G["Take fraction = remaining / weight
value += fraction * v_i, remaining = 0"]
    F --> H{"Remaining = 0, or no items left?"}
    G --> I["Stop: capacity exhausted"]
    H -->|"No, capacity and items remain"| D
    H -->|"Yes"| I
                

7. Correctness: The Exchange Argument

The claim to prove: if items are indexed so that $r_1 \ge r_2 \ge \cdots \ge r_n$, the greedy allocation — saturate item 1, then item 2, and so on until capacity runs out — achieves the maximum possible total value among all feasible allocations.

Trivial case. If $\sum_i w_i \le W$, every item can be taken fully; this is obviously optimal since no feasible allocation can exceed the sum of all values, and greedy achieves exactly that sum. The interesting case is $\sum_i w_i > W$, where the knapsack must be filled to exactly $W$ by some optimal allocation (any unused capacity could otherwise absorb more of any item and strictly increase value, so an optimal solution never leaves capacity unused when items remain available).

Proof by exchange (contradiction). Suppose, for contradiction, that some feasible allocation $S^\ast = (x_1^\ast,\dots,x_n^\ast)$ is optimal but is not the greedy allocation. Then there exist two items $i < j$ (so $r_i \ge r_j$ in sorted order, and $r_i > r_j$ unless they are tied) such that:

1. Item $i$ is not fully saturated in $S^\ast$: $x_i^\ast < w_i$, and
2. Item $j$ receives a positive amount in $S^\ast$: $x_j^\ast > 0$.

(If no such pair existed, every lower-ratio item with positive allocation would imply every higher-ratio item is already saturated, which is exactly the greedy allocation — the case we are assuming does not hold.)

Let $\delta = \min(w_i - x_i^\ast,\; x_j^\ast) > 0$. Construct a new allocation $S'$ identical to $S^\ast$ except:

$$x_i' = x_i^\ast + \delta \qquad x_j' = x_j^\ast - \delta$$

This is feasible: $x_i' \le w_i$ by choice of $\delta$, $x_j' \ge 0$ by choice of $\delta$, and total weight used is unchanged ($+\delta$ on item $i$ exactly cancels $-\delta$ on item $j$), so $\sum x' = \sum x^\ast \le W$ still holds. The change in total value is:

$$\Delta = \delta \cdot r_i - \delta \cdot r_j = \delta\,(r_i - r_j)$$

Since $r_i \ge r_j$, we have $\Delta \ge 0$; and whenever $r_i > r_j$ strictly, $\Delta > 0$, so $S'$ has strictly greater value than $S^\ast$ — contradicting the optimality of $S^\ast$. (When $r_i = r_j$ exactly, $\Delta = 0$: shifting weight between tied-ratio items never changes total value, which is why the greedy algorithm may break ties in any order.)

Conclusion. No optimal solution can have an unsaturated higher-ratio item alongside a positively-allocated lower-ratio item, except when their ratios are exactly tied. Applying this repeatedly (or by induction on the number of such "inversions") forces every optimal solution to saturate items in strictly decreasing ratio order until capacity is exhausted — which is precisely the allocation the greedy algorithm produces. Since at least one optimal solution exists and greedy's allocation is the only allocation (up to tie-breaking) consistent with the argument above, greedy's allocation is optimal. $\blacksquare$

Notice exactly where fractional divisibility is used: the constructed exchange amount $\delta$ can be any real number in $(0, \min(w_i - x_i^\ast, x_j^\ast)]$, because $x_i$ and $x_j$ are continuous variables. This flexibility is what lets the proof always find a strictly improving (or at least non-worsening) move. We return to why this breaks for 0/1 Knapsack in the next section.

8. Complexity Analysis

Why can 0/1 Knapsack not simply reuse this $O(n \log n)$ greedy algorithm and skip the $O(nW)$ DP table entirely? Because the exchange argument's proof depends on being able to shift an arbitrary amount $\delta$ of weight from one item to another. In 0/1 Knapsack, $x_i \in \{0, w_i\}$ only — there is no continuum of intermediate values to shift into or out of. If item $i$ is not yet taken ($x_i = 0$) and item $j$ is taken ($x_j = w_j$), the only "exchange" available is swapping item $j$ out completely and item $i$ in completely, which changes the total weight used by $w_i - w_j$ — not by an arbitrary small $\delta$ — and may not preserve feasibility at all. The proof's central step, "construct $S'$ by moving exactly $\delta$," is simply not expressible when items are atomic. Without that move, there is no way to show a greedy-by-ratio solution can always be improved into (or already is) the optimal one, and in fact it provably is not (see Comparison below). This is why 0/1 Knapsack needs the DP table over $(\text{item}, \text{capacity})$ states instead of a sort-and-scan.

9. Implementation

Each panel sorts items by ratio, then greedily fills the knapsack, returning both the total value and the fraction taken of each item. All three panels use the five-lot example above and reproduce the total value of 82 traced by hand.

def fractional_knapsack(weights, values, capacity):
    """
    Greedy Fractional Knapsack.
    Returns (total_value, fractions) where fractions[i] in [0, 1]
    is the portion of item i that was loaded.
    Time: O(n log n) for the sort, O(n) for the fill.
    """
    n = len(weights)
    if n == 0 or capacity <= 0:
        return 0.0, [0.0] * n

    # Sort item indices by decreasing value/weight ratio
    order = sorted(range(n), key=lambda i: values[i] / weights[i], reverse=True)

    remaining = capacity
    total_value = 0.0
    fractions = [0.0] * n

    for i in order:
        if remaining <= 0:
            break
        take = min(weights[i], remaining)
        fraction = take / weights[i]
        fractions[i] = fraction
        total_value += fraction * values[i]
        remaining -= take

    return total_value, fractions


weights = [4, 5, 6, 3, 8]
values = [40, 30, 24, 9, 8]
capacity = 12

total_value, fractions = fractional_knapsack(weights, values, capacity)
print("Total value:", total_value)   # 82.0
print("Fractions taken:", fractions)  # [1.0, 1.0, 0.5, 0.0, 0.0]

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>

struct Item { double weight; double value; };

// Greedy Fractional Knapsack.
// Fills `fractions[i]` with the portion of item i taken, in [0, 1].
// Time: O(n log n) for the sort, O(n) for the fill.
double fractionalKnapsack(const std::vector<Item>& items, double capacity,
                          std::vector<double>& fractions) {
    std::size_t n = items.size();
    fractions.assign(n, 0.0);

    std::vector<std::size_t> order(n);
    std::iota(order.begin(), order.end(), 0);
    std::sort(order.begin(), order.end(), [&](std::size_t a, std::size_t b) {
        return (items[a].value / items[a].weight) > (items[b].value / items[b].weight);
    });

    double remaining = capacity;
    double totalValue = 0.0;
    for (std::size_t idx : order) {
        if (remaining <= 0) break;
        double take = std::min(items[idx].weight, remaining);
        double fraction = take / items[idx].weight;
        fractions[idx] = fraction;
        totalValue += fraction * items[idx].value;
        remaining -= take;
    }
    return totalValue;
}

int main() {
    std::vector<Item> items = {{4, 40}, {5, 30}, {6, 24}, {3, 9}, {8, 8}};
    double capacity = 12;
    std::vector<double> fractions;

    double totalValue = fractionalKnapsack(items, capacity, fractions);
    std::cout << "Total value: " << totalValue << "\n";  // 82
    for (std::size_t i = 0; i < fractions.size(); ++i) {
        std::cout << "Item " << i << " fraction taken: " << fractions[i] << "\n";
    }
}

import java.util.Arrays;

public class FractionalKnapsack {

    // Greedy Fractional Knapsack.
    // Fills fractions[i] with the portion of item i taken, in [0, 1].
    // Time: O(n log n) for the sort, O(n) for the fill.
    static double solve(double[] weights, double[] values, double capacity, double[] fractions) {
        int n = weights.length;
        Integer[] order = new Integer[n];
        for (int i = 0; i < n; i++) {
            order[i] = i;
        }
        Arrays.sort(order, (a, b) ->
            Double.compare(values[b] / weights[b], values[a] / weights[a]));

        double remaining = capacity;
        double totalValue = 0.0;
        for (int idx : order) {
            if (remaining <= 0) break;
            double take = Math.min(weights[idx], remaining);
            double fraction = take / weights[idx];
            fractions[idx] = fraction;
            totalValue += fraction * values[idx];
            remaining -= take;
        }
        return totalValue;
    }

    public static void main(String[] args) {
        double[] weights = {4, 5, 6, 3, 8};
        double[] values = {40, 30, 24, 9, 8};
        double capacity = 12;
        double[] fractions = new double[weights.length];

        double totalValue = solve(weights, values, capacity, fractions);
        System.out.println("Total value: " + totalValue);              // 82.0
        System.out.println("Fractions taken: " + Arrays.toString(fractions));
        // [1.0, 1.0, 0.5, 0.0, 0.0]
    }
}

10. Testing and Edge Cases

11. Applications and Alternatives

When items are not divisible — unique machines, whole shipping containers, indivisible contracts — this greedy rule does not apply, and you need 0/1 Knapsack's dynamic programming (or, for larger inputs, approximation schemes) instead. Section 12 makes that boundary concrete.

12. Comparison With 0/1 Knapsack

The two problems look almost identical on paper — same inputs, same objective — but only one of them is greedy-solvable. Below, "greedy-by-ratio adapted for 0/1" means: sort by ratio, take an item fully if it still fits, otherwise skip it entirely (no fractions allowed) and move to the next.

A concrete counterexample

Take three items with $(w, v)$ pairs $(10, 60)$, $(20, 100)$, $(30, 120)$ and capacity $W = 50$. Their ratios are $6$, $5$, and $4$ respectively, so ratio order is already $A, B, C$.

True 0/1 optimum (checked by enumerating all 8 subsets): taking $B$ and $C$ together costs weight $20+30=50 \le 50$ and yields value $100+120=\mathbf{220}$. No other feasible subset beats it (for example $A+B$ costs 30 and yields only 160; $A+B+C$ costs 60, which is infeasible).

Greedy-by-ratio adapted for 0/1 (skip what doesn't fit): take $A$ fully (weight 10, value 60, remaining 40); take $B$ fully (weight 20, value 100, remaining 20, running total 160); item $C$ needs weight 30 but only 20 remains, and 0/1 items cannot be partially taken, so $C$ is skipped. Final value: $\mathbf{160}$ — strictly less than the true optimum of 220. This is the classic demonstration that greedy fails on 0/1 Knapsack.

Naively running the fractional algorithm on this 0/1 instance (i.e. allowing $C$ to be split, which is not actually legal here): after $A$ and $B$ fully, 20 units of capacity remain and $C$ needs 30, so the fractional algorithm would take $20/30 = 0.667$ of $C$, worth $0.667 \times 120 \approx 80$, for a reported total of $160 + 80 = \mathbf{240}$. This number is higher than the true 0/1 optimum of 220 — and it is wrong for the 0/1 problem, because "taking two-thirds of item $C$" is not a feasible 0/1 allocation at all. It is only the value of the continuous relaxation, which always upper-bounds the 0/1 optimum ($240 \ge 220$) but is not itself achievable when items are indivisible.

Both failures trace back to the same root cause identified in the Complexity section: the exchange argument's improving move requires shifting an arbitrary amount of weight between two items, and atomic 0/1 items simply do not offer that move.

13. Exercises and Mastery

Easy

1. Compute the fractional knapsack solution by hand for weights $[2, 3, 5, 7]$, values $[10, 18, 20, 14]$, and capacity $10$. Verify your answer against the Python implementation above.
2. State the ratio-sorted order for the item set above and explain why that order is forced by the exchange argument.

Medium

1. Suppose each item, if selected at all, must contribute at least 25% of its weight (a minimum-fraction constraint). Explain, conceptually, why the plain greedy scan can now produce an infeasible allocation near the capacity boundary, and describe what check you would add before accepting a partial item.
2. Prove that reordering two items with exactly equal ratio never changes the total value returned by the greedy algorithm.

Hard

1. Consider multiple knapsacks, each with its own capacity, and items that may be split across knapsacks as well as within a single knapsack. Is sorting once by global ratio and greedily filling knapsack after knapsack still guaranteed optimal? Sketch an argument or a small scenario suggesting why interactions between knapsacks' remaining capacities might require more than a single global ratio order (you do not need a full algorithm, only a well-reasoned argument either way).

Review rhythm: tomorrow, reconstruct the exchange argument from memory without looking back. Next week, implement the greedy scan in all three languages without referring to this page. Several weeks later, recognize the same "sort by ratio, take greedily, prove with an exchange argument" pattern in an unfamiliar scheduling or allocation problem. Finally, explain to someone who already knows 0/1 Knapsack exactly why this problem does not need dynamic programming.

14. Summary Cheat Sheet

• Fractional Knapsack allows any $x_i \in [0, w_i]$; 0/1 Knapsack restricts $x_i \in \{0, w_i\}$.
• Greedy rule: sort by decreasing value-to-weight ratio $r_i = v_i/w_i$, then take as much of each item as fits before moving to the next.
• Correctness comes from an exchange argument: shifting weight $\delta$ from a lower-ratio item to an unsaturated higher-ratio item never decreases total value, so any optimal solution must match the greedy allocation.
• Complexity is $O(n \log n)$, dominated entirely by the sort.
• 0/1 Knapsack cannot reuse this greedy rule: its atomic items admit no arbitrary-$\delta$ shift, so the same exchange proof fails, and it requires $O(nW)$ dynamic programming instead.
• A concrete instance $(10,60), (20,100), (30,120)$ with capacity 50 shows greedy-by-ratio giving 160 (too low) when adapted to skip infeasible 0/1 items, or 240 (too high and infeasible) when the fractional relaxation is misapplied — against a true 0/1 optimum of 220.