☕ DSA Java Articles

Topics › Greedy Algorithms › Easy Problems

Fractional Knapsack

Medium TUF ID 489 A2ZSDE

Java source ↗ Edit this article ↗

Problem

You have n items. Item i has value val[i] and weight wt[i]. A bag can carry total weight at most capacity. Unlike the 0/1 knapsack, you may take any fraction of an item: taking a fraction f (with 0 ≤ f ≤ 1) of item i adds f · val[i] to the value and f · wt[i] to the weight. Return the maximum total value you can carry, as a double.

Constraints (GeeksforGeeks version): 1 ≤ n ≤ 10^5, 1 ≤ val[i], wt[i] ≤ 10^4, 1 ≤ capacity ≤ 10^9. Weights are strictly positive, so every value-per-weight ratio is defined. Answers are accepted within a small tolerance such as 10^-6.

Example 1

val = [60, 100, 120], wt = [10, 20, 30], capacity = 50
answer = 240.0      // all of items 0 and 1 (value 160, weight 30), then 20/30 of item 2 (value 80)

Example 2

val = [60, 100], wt = [10, 20], capacity = 50
answer = 160.0      // everything fits, so take everything

Why a greedy choice is safe here

Imagine cutting every item into slices of one unit of weight. A slice of item i is worth val[i] / wt[i], its ratio. The bag holds capacity slices, so the best you can do is take the capacity most valuable slices. That means: take slices from the highest-ratio item first, then the next highest, and so on, and cut the last item you touch to fit exactly.

The same idea as an exchange argument: suppose an optimal packing takes some weight ε of a lower-ratio item L while leaving some weight of a higher-ratio item H behind. Swap ε of L for ε of H. The weight is unchanged and the value changes by ε · (ratio(H) - ratio(L)) ≥ 0. Repeating the swap turns any optimal packing into the greedy one without losing value.

This argument breaks for the 0/1 knapsack, because you cannot swap a small piece of an item. With the same three items and capacity 50, the 0/1 optimum is 220 (items 1 and 2), while greedy-by-ratio would take items 0 and 1 for only 160 and then be unable to fit item 2. Fractions are exactly what make greedy correct.

Approach 1: Greedy with a linear scan each round

Intuition. Implement the rule literally: while the bag has room, look through every item not yet used and pick the one with the highest ratio. Take all of it if it fits, otherwise take just enough to fill the bag.

To compare val[i] / wt[i] with val[best] / wt[best] we cross-multiply: val[i] · wt[best] > val[best] · wt[i]. Both weights are positive, so the inequality direction is preserved, and doing it in long avoids both floating-point rounding and int overflow (values up to 10^9 in the tests give products up to 10^18).

Algorithm.

  1. Mark every item as not taken. Set left = capacity, total = 0.
  2. While left > 0:
    • Scan all items that are not taken and find best, the one with the largest ratio. If there is none, stop.
    • Mark it taken. If wt[best] ≤ left, add val[best] and subtract its weight. Otherwise add val[best] · left / wt[best] and set left = 0.
  3. Return total.
static double greedyScan(int[] val, int[] wt, int capacity) {
    int n = val.length;
    boolean[] taken = new boolean[n];
    double total = 0;
    int left = capacity;
    while (left > 0) {
        int best = -1;
        for (int i = 0; i < n; i++) {
            if (taken[i]) continue;
            // val[i]/wt[i] > val[best]/wt[best], cross-multiplied in long to avoid division
            if (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
        taken[best] = true;
        if (wt[best] <= left) {
            total += val[best];
            left -= wt[best];
        } else {
            total += (double) val[best] * left / wt[best];
            left = 0;
        }
    }
    return total;
}

Complexity. Time O(n^2): up to n rounds, each scanning n items. Space O(n) for the taken flags.

The order in which items are chosen never changes between rounds, yet we recompute it every round. Sorting once removes that waste.

Approach 2: Optimal, sort by ratio once

Intuition. Sort item indices by ratio in descending order, then walk through them filling the bag. Every item before the last one touched goes in whole; the last one is cut to fit; everything after it is left out.

We sort an Integer[] of indices rather than the arrays themselves so val[i] and wt[i] stay paired. The comparator again cross-multiplies in long: a should come before b when val[a] · wt[b] > val[b] · wt[a], so it returns Long.compare(val[b] · wt[a], val[a] · wt[b]).

Algorithm.

  1. Build order = [0, 1, ..., n - 1] and sort it by ratio, highest first.
  2. For each index i in that order, while left > 0:
    • If wt[i] ≤ left, take it whole.
    • Otherwise take the fraction left / wt[i], adding val[i] · left / wt[i], and set left = 0.
  3. Return total.
static double optimal(int[] val, int[] wt, int capacity) {
    int n = val.length;
    Integer[] order = new Integer[n];
    for (int i = 0; i < n; i++) order[i] = i;
    // descending by val/wt; comparing val[a]*wt[b] with val[b]*wt[a] keeps the order exact
    Arrays.sort(order, (a, b) -> Long.compare((long) val[b] * wt[a], (long) val[a] * wt[b]));
    double total = 0;
    int left = capacity;
    for (int i : order) {
        if (left == 0) break;
        if (wt[i] <= left) {
            total += val[i];
            left -= wt[i];
        } else {
            total += (double) val[i] * left / wt[i];
            left = 0;
        }
    }
    return total;
}

Dry run on Example 1. Ratios are 6, 5 and 4, so the order is items 0, 1, 2.

item ratio wt left before taken value added total
0 6 10 50 all 10 60 60
1 5 20 40 all 20 100 160
2 4 30 20 20 of 30 80 240

Complexity. Time O(n log n) for the sort; the fill loop is O(n). Space O(n) for the boxed index array.

Edge cases and pitfalls