Fractional Knapsack

Given items with weights and values and a knapsack capacity, maximize total value when you may take fractions of items. The classic greedy solution sorts by value-to-weight ratio and fills the knapsack greedily. This lesson covers the algorithm, proof sketch, comparison with 0-1 knapsack, and implementations in C, Java, and Python with trace tables.

Overview

Imagine a backpack with limited weight capacity. Each item has a weight and a value. In the fractional version, you can take part of an item (e.g. half a gold bar). The greedy strategy always takes the “best bang for buck” first — items with the highest value / weight ratio.

Knapsack capacity W = 50

Item   weight   value   ratio (v/w)
  A       10      60        6.0   ← take all
  B       20     100        5.0   ← take all
  C       30     120        4.0   ← take 20/30 (partial)

Greedy total value = 60 + 100 + 80 = 240

Problem Statement

Input: n items with weights w[i] and values v[i], and knapsack capacity W.

Output: Maximum total value achievable, allowing fractions of items (each item can be used in proportion from 0 to 1).

Constraint: Total weight taken ≤ W.

Complexity target: O(n log n) for sorting + O(n) greedy fill; O(n) extra space if storing fractions per item.

Greedy Algorithm

1. Compute ratio[i] = value[i] / weight[i] for each item.
2. Sort items by decreasing ratio.
3. Initialize remaining = W and total_value = 0.
4. For each item in sorted order:
   • If weight[i] ≤ remaining, take the whole item.
   • Else take fraction remaining / weight[i] and stop.

Why Greedy Works

Exchange argument (sketch): Suppose an optimal solution uses less than the full available amount of the highest-ratio item while some lower-ratio item is included. Replace a small weight δ from the lower-ratio item with δ from the higher-ratio item — total value increases. Repeat until the greedy choice is matched. Hence the ratio-greedy solution is optimal.

Code (C, Java, Python)

Python

def fractional_knapsack(items, capacity):
    """Max value with fractional items — sort by value/weight ratio. O(n log n)."""
    items = sorted(items, key=lambda x: x[1] / x[0], reverse=True)
    total_value = 0.0
    remaining = capacity
    picks = []

    for weight, value in items:
        if remaining <= 0:
            break
        ratio = value / weight
        if weight <= remaining:
            total_value += value
            remaining -= weight
            picks.append((weight, value, 1.0))
        else:
            frac = remaining / weight
            total_value += value * frac
            picks.append((weight, value, frac))
            remaining = 0

    return total_value, picks


if __name__ == "__main__":
    items = [(10, 60), (20, 100), (30, 120)]
    val, picks = fractional_knapsack(items, 50)
    print(f"max value = {val:.1f}, picks = {picks}")  # 240.0

Java

import java.util.Arrays;
import java.util.Comparator;

public class FractionalKnapsack {

    /** Sort by decreasing value/weight; greedily fill knapsack. */
    public static double maxValue(int[][] items, int capacity) {
        Integer[] idx = new Integer[items.length];
        for (int i = 0; i < items.length; i++) idx[i] = i;

        Arrays.sort(idx, Comparator.comparingDouble(
            i -> -(double) items[i][1] / items[i][0]));

        double total = 0.0;
        int remaining = capacity;

        for (int i : idx) {
            int w = items[i][0], v = items[i][1];
            if (remaining <= 0) break;
            if (w <= remaining) {
                total += v;
                remaining -= w;
            } else {
                total += v * ((double) remaining / w);
                break;
            }
        }
        return total;
    }

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

C

#include <stdio.h>
#include <stdlib.h>

typedef struct { int weight, value; } Item;

int cmp_ratio_desc(const void *a, const void *b) {
    Item *x = (Item *)a, *y = (Item *)b;
    double rx = (double)x->value / x->weight;
    double ry = (double)y->value / y->weight;
    return (ry > rx) - (ry < rx);
}

double fractional_knapsack(Item items[], int n, int capacity) {
    qsort(items, n, sizeof(Item), cmp_ratio_desc);
    double total = 0.0;
    int remaining = capacity, i;

    for (i = 0; i < n && remaining > 0; i++) {
        if (items[i].weight <= remaining) {
            total += items[i].value;
            remaining -= items[i].weight;
        } else {
            total += items[i].value * ((double)remaining / items[i].weight);
            remaining = 0;
        }
    }
    return total;
}

int main(void) {
    Item items[] = {{10, 60}, {20, 100}, {30, 120}};
    printf("%.1f\n", fractional_knapsack(items, 3, 50)); /* 240.0 */
    return 0;
}

Output & Trace

Ratio table — capacity W = 50

Greedy trace

Program output (more examples)

0-1 vs Fractional Knapsack

Variants & Related Problems

Approach Comparison

Real-Life Applications

Interview Tips

1. Clarify first: Can items be split? If yes → fractional greedy; if no → DP.
2. State algorithm: compute ratios, sort descending, fill knapsack greedily.
3. Watch for floating point — use double in C/Java; avoid integer division when computing ratios.
4. Give the 0-1 counterexample if asked why greedy fails without fractions.
5. Complexity: O(n log n) time, O(1) extra if sorting in place.
6. Connect to activity selection (another classic greedy) and coin change (different greedy rules).