Fractional Knapsack — Editorial

Opening the reading…

Intuitionwhy density determines every choice

An item is not valuable merely because its total value is large. Since items can be split, the useful quantity is value per unit of weight: val[i] / wt[i]. An item worth 6 per unit weight is always a better use of the next unit of capacity than an item worth 4, regardless of their total sizes.

Take items in descending order of this density. If the next item fits, take it completely. If it does not fit, take exactly the fraction that fills the remaining capacity and stop. Any capacity assigned to a lower-density item while a higher-density item remains available could be exchanged for the higher-density material and would not reduce the total value.

Approachsort once, then fill the capacity

Create an index order containing every item, because sorting the indices preserves the original value and weight arrays while giving the scan a density order.

Sort the indices by descending value-to-weight ratio, comparing val[a] * wt[b] with val[b] * wt[a] so the ordering does not depend on floating-point division.

Set remaining to capacity and answer to zero, because every later decision only needs the unused weight and the value accumulated so far.

Visit the items in sorted order and take min(remaining, wt[id]) weight from each one, because taking more than the remaining capacity would violate the constraint while taking less would leave profitable material unused.

Add taken * val[id] / wt[id] to the answer, using floating-point arithmetic because the final item may contribute a non-integer fraction of its value.

Subtract taken from remaining and stop when remaining reaches zero, because all capacity has then been assigned and no later item can improve the result.

Complexitythe sort dominates the scan

MEASURE	BOUND	WHY
Time	O(n log n)	Building the order takes O(n), sorting n indices takes O(n log n), and the final scan examines each sorted index at most once. The sorting term dominates, regardless of which item becomes fractional.
Space	O(n) extra	The index order stores one integer per item, while the answer and remaining capacity use constant extra space. The returned numeric value is required output and is excluded from the space bound; the extra space remains O(n) for every input shape.

Here n is the number of items.

Annotated solutionC++ · index sorting with cross-product comparison

CPPSort item indices by density, then take each item completely or take the final fitting fraction.

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

class Solution {
public:
    double fractionalKnapsack(vector<int>& val, vector<int>& wt, int capacity) {
        int n = static_cast<int>(val.size());
        vector<int> order(n);

        for (int i = 0; i < n; ++i) {
            order[i] = i;
        }

        sort(order.begin(), order.end(), [&](int a, int b) {
            long long left = 1LL * val[a] * wt[b];
            long long right = 1LL * val[b] * wt[a];

            if (left != right) {
                return left > right;
            }
            return a < b;
        });

        long double answer = 0.0L;
        long long remaining = capacity;

        for (int id : order) {
            if (remaining == 0) {
                break;
            }

            long long taken = min(remaining, static_cast<long long>(wt[id]));
            answer += static_cast<long double>(taken) * val[id] / wt[id];
            remaining -= taken;
        }

        return static_cast<double>(answer);
    }
};

The comparator avoids calculating val[i] / wt[i] while sorting. Comparing val[a] / wt[a] and val[b] / wt[b] directly would require division and can introduce unnecessary precision concerns; cross multiplication compares the same fractions exactly. The 1LL cast makes the products long long, and the accumulation uses long double so fractional contributions retain more precision before the required double return.