Fractional Knapsack
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.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
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.
| Approach | Time | Space |
|---|---|---|
| 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?
O(n · W)O(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.
- Compare: 0/1 DP answers 220 on the first example, while splitting reaches 240.
2Optimal (greedy by ratio)
O(n log n)O(n)Sort items by val / wt descending. Take whole items while they fit; take the fraction that fits of the next one, then stop.
- Sort indices by ratio, descending.
- 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;
}
}class Solution:
def fractionalKnapsack(self, val: List[int], wt: List[int], capacity: int) -> float:
n = len(val)
idx = sorted(range(n), key=lambda i: -(val[i] / wt[i]))
total = 0.0
left = capacity
for i in idx:
if left == 0:
break
if wt[i] <= left:
total += val[i]
left -= wt[i]
else:
total += val[i] * left / wt[i]
left = 0
return totalclass Solution {
public:
double fractionalKnapsack(vector<int>& val, vector<int>& wt, long long capacity) {
int n = val.size();
vector<int> idx(n);
for (int i = 0; i < n; i++) idx[i] = i;
stable_sort(idx.begin(), idx.end(), [&](int a, int b) {
return (double) val[a] / wt[a] > (double) val[b] / wt[b];
});
double total = 0;
long 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;
}
};function fractionalKnapsack(val, wt, capacity) {
const n = val.length;
const idx = [];
for (let i = 0; i < n; i++) idx.push(i);
idx.sort((a, b) => val[b] / wt[b] - val[a] / wt[a]);
let total = 0;
let left = capacity;
for (const i of idx) {
if (left === 0) break;
if (wt[i] <= left) { total += val[i]; left -= wt[i]; }
else { total += 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.