Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

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

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

  1. Because items can be split, value per unit of weight is all that matters.
  2. 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));
    }
}

Solve Fractional Knapsack online · All practice problems