Fractional Knapsack

Given n items, each with a value and a weight, and a knapsack that holds at most capacity weight, find the largest total value that fits. Items can be split: taking a fraction f of an item gives f × value for f × weight.

Example

Text

items (value, weight) = [(60, 10), (100, 20), (120, 30)], capacity = 50
Output: 240   (all of the first two, then 20/30 of the third: 60 + 100 + 80)

Brute force: try every filling order

A record is a short way to declare a class with read-only fields (value() and weight() read them). Any filling can be described by an order: take items whole in that order until the next one doesn't fit, then take the fraction of it that does. The best filling is the best over all n! orders.

Java

import java.util.ArrayList;
import java.util.List;

public class Main {
    record Item(double value, double weight) {}

    static double fill(List<Item> items, List<Integer> order, double capacity) {
        double value = 0.0;
        for (int i : order) {
            Item item = items.get(i);
            double take = Math.min(item.weight(), capacity);
            value += item.value() * take / item.weight();
            capacity -= take;
        }
        return value;
    }

    static double best(List<Item> items, List<Integer> order, boolean[] used, double capacity) {
        if (order.size() == items.size()) {
            return fill(items, order, capacity);
        }
        double result = 0.0;
        for (int i = 0; i < items.size(); i++) {
            if (!used[i]) {
                used[i] = true;
                order.add(i);
                result = Math.max(result, best(items, order, used, capacity));
                order.remove(order.size() - 1);
                used[i] = false;
            }
        }
        return result;
    }

    static double maxValue(List<Item> items, double capacity) {
        return best(items, new ArrayList<>(), new boolean[items.size()], capacity);
    }

    public static void main(String[] args) {
        List<Item> items = List.of(new Item(60, 10), new Item(100, 20), new Item(120, 30));
        System.out.println(maxValue(items, 50));
    }
}

Output

240.0

Time: O(n! · n). Space: O(n).

Optimal: best value per weight first

Every unit of capacity should hold the most valuable weight available. That's the item with the highest value per unit of weight (value / weight), so take items in decreasing order of that ratio, and split only the last one.

item	value	weight	value / weight
0	60	10	6
1	100	20	5
2	120	30	4

Take item 0 (capacity left 40), item 1 (left 20), then 20 of item 2's 30 units: 60 + 100 + 120 × 20/30 = 240.

If an optimal filling used some weight of a lower-ratio item while a higher-ratio item wasn't fully taken, swapping that weight between them would increase the value, which contradicts optimality. So the greedy order can't be beaten.

Java

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;

public class Main {
    record Item(double value, double weight) {}

    static double maxValue(List<Item> items, double capacity) {
        List<Item> byRatio = new ArrayList<>(items);
        byRatio.sort(Comparator.comparingDouble((Item it) -> it.value() / it.weight()).reversed()); // highest ratio first
        double value = 0.0;
        for (Item item : byRatio) {
            if (capacity <= 0.0) break;
            double take = Math.min(item.weight(), capacity);
            value += item.value() * take / item.weight();
            capacity -= take;
        }
        return value;
    }

    public static void main(String[] args) {
        List<Item> items = List.of(new Item(60, 10), new Item(100, 20), new Item(120, 30));
        System.out.println(maxValue(items, 50));
        System.out.println(maxValue(List.of(new Item(500, 30)), 10) + " " + maxValue(List.of(new Item(10, 5), new Item(40, 4)), 100));
    }
}

Output

240.0
166.66666666666666 50.0

Time: O(n log n) for the sort. Space: O(n) for the sorted copy.

Comparator.comparingDouble builds a comparator from a function that returns a double, and reversed() flips it to put the highest ratio first. It orders values with Double.compare, so a NaN ratio (from 0 / 0) sorts after every other value instead of breaking the sort. Subtracting two ratios is never used as a comparator, because the result of such a subtraction can be rounded to 0.

Edge cases

Everything fits: the answer is the sum of all values.
Items can't be split: this is the 0/1 knapsack, where greedy fails. In the example, greedy would take items 0 and 1 for 160, but items 1 and 2 give 220. It needs dynamic programming, as in Partition Equal Subset Sum.
Zero-weight items: the ratio divides by zero. With double, that gives infinity (or NaN when the value is also 0) instead of an exception. Take them all first, as they cost no capacity. The code above does not guard this case, and take * value / weight would be NaN for such an item.