Practice › Greedy
Fractional Knapsack
Medium · Greedy · Asked at Amazon, Microsoft, Flipkart, TCS, Infosys
Each item has a value and a weight, and you may take any fraction of an item. Print the maximum total value that fits in a bag of capacity W, with exactly 2 digits after the decimal point.
Input
First line: n W. Next n lines: value weight.
Output
The maximum value, e.g. 240.00.
Constraints
- 1 ≤ n ≤ 10^5
- 1 ≤ W ≤ 10^9
- 1 ≤ value, weight ≤ 10^4
Sort items by value/weight (highest first). Take whole items while they fit, then a fraction of the next one.
Example 1
Input
3 50 60 10 100 20 120 30
Output
240.00
Example 2
Input
2 50 60 10 100 20
Output
160.00
Hints
- Because items can be split, value per unit of weight is all that matters.
- Sort by value/weight descending, take whole items while they fit, then the needed fraction of the next item.
Approach
Sort items by ratio v / w (compare v1·w2 with v2·w1 to avoid floating-point issues while sorting). Take each item whole while capacity remains; for the first item that does not fit, take the fraction remaining / w of its value and stop. Print with two decimals.
Complexity: O(n log n) time · O(n) space
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
long long W;
cin >> n >> W;
vector<pair<long long, long long>> it(n); // (value, weight)
for (auto &x : it) cin >> x.first >> x.second;
sort(it.begin(), it.end(), [](const pair<long long, long long> &a, const pair<long long, long long> &b) {
return a.first * b.second > b.first * a.second;
});
double total = 0;
for (auto &x : it) {
if (W <= 0) break;
long long take = min(x.second, W);
total += (double)x.first * take / x.second;
W -= take;
}
printf("%.2f\n", total);
return 0;
}Python solution
import sys
from functools import cmp_to_key
data = list(map(int, sys.stdin.read().split()))
n, W = data[0], data[1]
items = [(data[2 + 2 * i], data[3 + 2 * i]) for i in range(n)]
items.sort(key=cmp_to_key(lambda a, b: b[0] * a[1] - a[0] * b[1]))
total = 0.0
for v, w in items:
if W <= 0:
break
take = min(w, W)
total += v * take / w
W -= take
print(f"{total:.2f}")Java solution
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
long W = sc.nextLong();
long[][] it = new long[n][2];
for (int i = 0; i < n; i++) {
it[i][0] = sc.nextLong();
it[i][1] = sc.nextLong();
}
Arrays.sort(it, (a, b) -> Long.compare(b[0] * a[1], a[0] * b[1]));
double total = 0;
for (long[] x : it) {
if (W <= 0) break;
long take = Math.min(x[1], W);
total += (double) x[0] * take / x[1];
W -= take;
}
System.out.println(String.format(Locale.ROOT, "%.2f", total));
}
}