Fractional Knapsack Problem

The problem, simply

You get n items. Each item has a weight and a value. Your bag can carry at most W kilos. You may cut an item and take only part of it: half the weight gives half the value.

Give back the largest total value you can put in the bag.

A story to remember it

Picture it

Examples

Way 1: the simple way

Some order of filling must be the best one. So try every order. For each order, put items in one by one, whole if they fit, and cut the first one that does not fit. Remember the best total.

1. List every order of the n items.
2. For each order, fill the bag and cut the last piece.
3. Keep the biggest value.

class Solution {
    private double best = 0;

    public double fractionalKnapsack(int[] weight, int[] value, int W) {
        best = 0;
        int n = weight.length;
        int[] order = new int[n];
        for (int i = 0; i < n; i++) order[i] = i;
        permute(order, 0, weight, value, W);
        return best;
    }

    private void permute(int[] order, int k, int[] wt, int[] val, int W) {
        if (k == order.length) {
            best = Math.max(best, fill(order, wt, val, W));
            return;
        }
        for (int i = k; i < order.length; i++) {
            swap(order, k, i);
            permute(order, k + 1, wt, val, W);
            swap(order, k, i);
        }
    }

    private double fill(int[] order, int[] wt, int[] val, int W) {
        double room = W, total = 0;
        for (int i : order) {
            if (room == 0) break;
            double take = Math.min(room, wt[i]);   // whole item, or the part that fits
            total += take / wt[i] * val[i];
            room -= take;
        }
        return total;
    }

    private void swap(int[] a, int i, int j) { int t = a[i]; a[i] = a[j]; a[j] = t; }
}

How long it takes: n! orders, each filled in O(n), O(n! * n). Extra room: the order array and the recursion, O(n).

Way 2: the clever way

Only one order matters: best value per kilo first.

1. Work out value / weight for every item.
2. Sort the items by that number, biggest first.
3. Walk the sorted items. If the whole item fits, take it. If not, take the part that fits and stop.

Why does this work? Suppose your bag has a kilo of something worth less per kilo while a better item is still not fully in. Swap that kilo for a kilo of the better item. The weight stays the same and the value goes up. So the best bag never has such a kilo, and that is exactly the bag the greedy builds.

class Solution {
    public double fractionalKnapsack(int[] weight, int[] value, int W) {
        int n = weight.length;
        Integer[] order = new Integer[n];
        for (int i = 0; i < n; i++) order[i] = i;
        // best value per kilo first: compare v[a]/w[a] with v[b]/w[b] by cross multiplying
        Arrays.sort(order, (a, b) -> Long.compare((long) value[b] * weight[a],
                                                  (long) value[a] * weight[b]));

        double total = 0;
        long room = W;
        for (int i : order) {
            if (room == 0) break;
            if (weight[i] <= room) {            // the whole item fits
                total += value[i];
                room -= weight[i];
            } else {                             // cut the part that fits
                total += (double) value[i] * room / weight[i];
                room = 0;
            }
        }
        return total;
    }
}

How long it takes: the sort is O(n log n) and the walk is O(n), so O(n log n). Extra room: the order array, O(n).

Watch out for

• Integer division. value / weight on two ints rounds down, so 5/2 and 2/1 look the same. Use doubles, or compare by cross multiplying as in the code.
• Cross multiplying can overflow int. Cast to long first.
• An item with weight 0 has an endless value per kilo. Take it for free before sorting, or the division breaks.
• Return a double. Many judges want it printed with a fixed number of decimals.

What interviewers ask next

• Can you beat O(n log n)? Yes, O(n) on average. Use quickselect to find the item where the bag runs out, without sorting everything.
• What changes for 0/1 knapsack? Greedy no longer works. Use dynamic programming over capacity, O(n * W).
• How is this related to linear programming? Fractional knapsack is a tiny linear program, and the greedy is its exact solution.
• What if there are many bags? With cuts allowed it is still easy: treat all bags as one big bag of the total size and fill by value per kilo.

Remember this

Grown-up words: the bag is the knapsack, value per kilo is the value to weight ratio, cutting items makes this the fractional knapsack, and the swap a kilo argument is an exchange argument.