Fractional Knapsack

Greedy O(n log n) O(1)

Maximizes value under a weight limit when items can be split: take items in value/weight order, breaking the last one.

w10 · v606.0/kg—

w20 · v1005.0/kg—

w30 · v1204.0/kg—

Bag0/50

capacity 50total0

1/13

Items are sorted by value/weight ratio — best value per kg first.

InvariantThe bag holds the best value per unit of weight taken so far; splitting one item is what makes greedy optimal here.

consideringtaken wholetaken fraction

fractional-knapsack.c

/* items sorted by value/weight ratio (desc) */
double fracKnapsack(int w[], int v[], int n, int W) {
    double total = 0;
    int remaining = W;
    for (int i = 0; i < n && remaining > 0; i++) {
        if (w[i] <= remaining) {
            remaining -= w[i];       /* take it all */
            total += v[i];
        } else {
            double frac = (double)remaining / w[i];
            total += v[i] * frac;    /* take a fraction */
            remaining = 0;
        }
    }
    return total;
}

How Fractional Knapsack works

Best value per kilogram first. Take whole items while they fit, then top the bag off with a fraction of the next one — divisibility is what makes the greedy choice provably optimal.

When to use it

Divisible resources: liquids, budgets, bandwidth allocation. (Indivisible items need 0/1 knapsack DP.)