Start practising

Fractional Knapsack

Medium Dynamic Programming Knapsack Original on GeeksforGeeks

Fractional Knapsack is a medium dynamic programming problem solved with the knapsack pattern. The best approach, optimal (greedy by ratio), runs in O(n log n) time and O(n) space. Below are 2 approaches in Java, from why not the 0/1 dp? up.

Problem

Same as the knapsack problem, except you may take a fraction of any item (getting that fraction of its value). Maximise the total value within capacity W.

Examples

Example 1

Input
val = [60, 100, 120], wt = [10, 20, 30], W = 50
Output
240.0
Why
Take items 0 and 1 fully, and 2/3 of item 2.

Example 2

Input
val = [500], wt = [30], W = 10
Output
166.667

Constraints

  • 1 <= n <= 10^5; items can be split.

Animated walkthrough

A narrated, step-by-step animation that builds the solution from the idea up. Press play, or step through it at your own pace.

Concepts first, then the problem and every approach, step by step.

Space to play or pause · ← → to jump a step · click or drag the bar to seek

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the Java code.

ApproachTimeSpace
Why not the 0/1 DP?O(n · W)O(W)
Optimal (greedy by ratio)O(n log n)O(n)

1Why not the 0/1 DP?

TimeO(n · W)
SpaceO(W)

The 0/1 knapsack DP treats each item as all-or-nothing, so it misses the value of splitting the last item. It also depends on W, which can be huge here. Because a fraction is allowed, a greedy exchange argument works: swapping any weight of a lower-ratio item for the same weight of a higher-ratio item never lowers the value.

  1. Compare: 0/1 DP answers 220 on the first example, while splitting reaches 240.

2Optimal (greedy by ratio)

TimeO(n log n)
SpaceO(n)

Sort items by val / wt descending. Take whole items while they fit; take the fraction that fits of the next one, then stop.

  1. Sort indices by ratio, descending.
  2. If wt <= remaining: take all. Else take remaining / wt of it and stop.
Java
class Solution {
    double fractionalKnapsack(int[] val, int[] wt, long capacity) {
        int n = val.length;
        Integer[] idx = new Integer[n];
        for (int i = 0; i < n; i++) idx[i] = i;
        Arrays.sort(idx, (a, b) -> Double.compare((double) val[b] / wt[b], (double) val[a] / wt[a]));
        double total = 0;
        long left = capacity;
        for (int i : idx) {
            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;
    }
}

Edge cases to test

  • Capacity larger than the total weight
  • Ties in value per weight

Hints

Hint 1

Because items can be split, greedy works: always take the item with the highest value per unit of weight.

FAQ

What is the best time complexity for Fractional Knapsack?

Optimal (greedy by ratio) runs in O(n log n) time and O(n) extra space.

Which pattern does Fractional Knapsack use?

It is a dynamic programming problem that uses the knapsack pattern. Other problems with the same pattern: 0 - 1 Knapsack Problem, Knapsack with Duplicate Items, Coin Change.

Is there a brute force solution for Fractional Knapsack?

Yes. Why not the 0/1 DP? takes O(n · W) time and O(W) space. The 0/1 knapsack DP treats each item as all-or-nothing, so it misses the value of splitting the last item.

Which edge cases should I test for Fractional Knapsack?

Capacity larger than the total weight; Ties in value per weight.