Fractional Knapsack

Brute Force — Scan for the Best Item, Every Round — Example 1, a 60 kg bag. Top row: item values, with value per kilogram underneath. Second row: kilograms still out of the bag.

#include <algorithm>
#include <vector>
using namespace std;

class Solution {
public:
    double fractionalKnapsack(vector<int>& val, vector<int>& wt, int capacity) {
        int n = val.size();
        vector<long long> left(wt.begin(), wt.end());  // kilograms of each item not yet in the bag
        double total = 0;
        long long cap = capacity;
        while (cap > 0) {
            int best = -1;
            for (int i = 0; i < n; i++)  // the item with the most value per kilogram among those not used up
                if (left[i] > 0 && (best == -1 || (long long)val[i] * wt[best] > (long long)val[best] * wt[i])) best = i;
            if (best == -1) break;  // every item is already in the bag
            long long take = min(left[best], cap);
            total += (double)val[best] * take / wt[best];
            left[best] -= take;
            cap -= take;
        }
        return total;
    }
};

class Solution:
    def fractionalKnapsack(self, val, wt, capacity):
        n = len(val)
        left = wt[:]  # kilograms of each item not yet in the bag
        total = 0.0
        while capacity > 0:
            best = -1
            for i in range(n):  # the item with the most value per kilogram among those not used up
                if left[i] > 0 and (best == -1 or val[i] * wt[best] > val[best] * wt[i]):
                    best = i
            if best == -1:  # every item is already in the bag
                break
            take = min(left[best], capacity)
            total += val[best] * take / wt[best]
            left[best] -= take
            capacity -= take
        return total

class Solution {
    public double fractionalKnapsack(int[] val, int[] wt, int capacity) {
        int n = val.length;
        long[] left = new long[n];  // kilograms of each item not yet in the bag
        for (int i = 0; i < n; i++) left[i] = wt[i];
        double total = 0;
        long cap = capacity;
        while (cap > 0) {
            int best = -1;
            for (int i = 0; i < n; i++)  // the item with the most value per kilogram among those not used up
                if (left[i] > 0 && (best == -1 || (long) val[i] * wt[best] > (long) val[best] * wt[i])) best = i;
            if (best == -1) break;  // every item is already in the bag
            long take = Math.min(left[best], cap);
            total += (double) val[best] * take / wt[best];
            left[best] -= take;
            cap -= take;
        }
        return total;
    }
}

Sort by Value per Kilogram, Then Fill — Example 1: the items are sorted once by value per kilogram, then taken from the left until the bag is full.

#include <algorithm>
#include <numeric>
#include <vector>
using namespace std;

class Solution {
public:
    double fractionalKnapsack(vector<int>& val, vector<int>& wt, int capacity) {
        vector<int> order(val.size());
        iota(order.begin(), order.end(), 0);
        sort(order.begin(), order.end(), [&](int a, int b) {  // a before b when val[a]/wt[a] > val[b]/wt[b], without dividing
            return (long long)val[a] * wt[b] > (long long)val[b] * wt[a];
        });
        double total = 0;
        long long cap = capacity;
        for (int i : order) {
            if (wt[i] <= cap) {  // the whole item fits
                total += val[i];
                cap -= wt[i];
            } else {  // only part of it fits, and then the bag is full
                total += (double)val[i] * cap / wt[i];
                break;
            }
        }
        return total;
    }
};

class Solution:
    def fractionalKnapsack(self, val, wt, capacity):
        # most value per kilogram first; with whole numbers up to 10^4, equal ratios give equal decimals
        order = sorted(range(len(val)), key=lambda i: val[i] / wt[i], reverse=True)
        total = 0.0
        for i in order:
            if wt[i] <= capacity:  # the whole item fits
                total += val[i]
                capacity -= wt[i]
            else:  # only part of it fits, and then the bag is full
                total += val[i] * capacity / wt[i]
                break
        return total

import java.util.Arrays;

class Solution {
    public double fractionalKnapsack(int[] val, int[] wt, int capacity) {
        Integer[] order = new Integer[val.length];
        for (int i = 0; i < order.length; i++) order[i] = i;
        // a before b when val[a]/wt[a] > val[b]/wt[b], compared without dividing
        Arrays.sort(order, (a, b) -> Long.compare((long) val[b] * wt[a], (long) val[a] * wt[b]));
        double total = 0;
        long cap = capacity;
        for (int i : order) {
            if (wt[i] <= cap) {  // the whole item fits
                total += val[i];
                cap -= wt[i];
            } else {  // only part of it fits, and then the bag is full
                total += (double) val[i] * cap / wt[i];
                break;
            }
        }
        return total;
    }
}

Find the Cut Item With a Random Pivot — Example 1. Each round picks a pivot, weighs the items that are better per kilogram, and keeps only the side where the bag fills up.

#include <numeric>
#include <random>
#include <vector>
using namespace std;

class Solution {
public:
    double fractionalKnapsack(vector<int>& val, vector<int>& wt, int capacity) {
        vector<int> items(val.size());
        iota(items.begin(), items.end(), 0);
        mt19937 rng(12345);
        double total = 0;
        long long cap = capacity;
        while (!items.empty() && cap > 0) {
            int p = items[rng() % items.size()];  // a random pivot keeps the expected work linear
            vector<int> better, worse;
            long long wBetter = 0, wSame = 0, vBetter = 0, vSame = 0;
            for (int i : items) {
                long long l = (long long)val[i] * wt[p], r = (long long)val[p] * wt[i];
                if (l > r) { better.push_back(i); wBetter += wt[i]; vBetter += val[i]; }
                else if (l == r) { wSame += wt[i]; vSame += val[i]; }
                else worse.push_back(i);
            }
            if (wBetter >= cap) {  // the bag fills up inside the better group
                items.swap(better);
                continue;
            }
            total += vBetter;  // every better item goes in whole
            cap -= wBetter;
            if (wSame >= cap) return total + (double)val[p] * cap / wt[p];  // the pivot's group fills the rest
            total += vSame;
            cap -= wSame;
            items.swap(worse);
        }
        return total;
    }
};

import random


class Solution:
    def fractionalKnapsack(self, val, wt, capacity):
        items = list(range(len(val)))
        total = 0.0
        while items and capacity > 0:
            p = random.choice(items)  # a random pivot keeps the expected work linear
            better = [i for i in items if val[i] * wt[p] > val[p] * wt[i]]
            same = [i for i in items if val[i] * wt[p] == val[p] * wt[i]]
            worse = [i for i in items if val[i] * wt[p] < val[p] * wt[i]]
            w_better = sum(wt[i] for i in better)
            if w_better >= capacity:  # the bag fills up inside the better group
                items = better
                continue
            total += sum(val[i] for i in better)  # every better item goes in whole
            capacity -= w_better
            w_same = sum(wt[i] for i in same)
            if w_same >= capacity:  # the pivot's group fills the rest; all of it has the pivot's value per kilogram
                return total + val[p] * capacity / wt[p]
            total += sum(val[i] for i in same)
            capacity -= w_same
            items = worse
        return total

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

class Solution {
    public double fractionalKnapsack(int[] val, int[] wt, int capacity) {
        List<Integer> items = new ArrayList<>();
        for (int i = 0; i < val.length; i++) items.add(i);
        Random rng = new Random(12345);
        double total = 0;
        long cap = capacity;
        while (!items.isEmpty() && cap > 0) {
            int p = items.get(rng.nextInt(items.size()));  // a random pivot keeps the expected work linear
            List<Integer> better = new ArrayList<>(), worse = new ArrayList<>();
            long wBetter = 0, wSame = 0, vBetter = 0, vSame = 0;
            for (int i : items) {
                long l = (long) val[i] * wt[p], r = (long) val[p] * wt[i];
                if (l > r) { better.add(i); wBetter += wt[i]; vBetter += val[i]; }
                else if (l == r) { wSame += wt[i]; vSame += val[i]; }
                else worse.add(i);
            }
            if (wBetter >= cap) {  // the bag fills up inside the better group
                items = better;
                continue;
            }
            total += vBetter;  // every better item goes in whole
            cap -= wBetter;
            if (wSame >= cap) return total + (double) val[p] * cap / wt[p];  // the pivot's group fills the rest
            total += vSame;
            cap -= wSame;
            items = worse;
        }
        return total;
    }
}