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, Python, C++ and JavaScript, 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.

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (2 examples, or your own). Submit also runs 10 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

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 code in Java, Python, C++ and JavaScript.

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.
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.