Fractional Knapsack & Greedy

1. Algorithm & Complexity

The Fractional Knapsack problem is: Given n items, each with weight w[i] and value v[i], and a knapsack of capacity C, maximize total value by taking whole items or fractions of items.

Greedy strategy (Dantzig’s algorithm):

  1. Compute ratio r[i] = v[i] / w[i] for each item.
  2. Sort all items in descending order of r[i].
  3. Iterate sorted items:
    • If w[i] ≤ remainingCapacity, take the whole item → add v[i], subtract w[i].
    • Else take fraction f = remainingCapacity / w[i] → add f * v[i], fill the knapsack, stop.

Time Complexity

  • Sorting by ratio: O(n log n)
  • Scanning items once: O(n)

Total: O(n log n)

Memory Complexity

  • Store n tuples and a few scalars → O(n)

2. Two Easy Codeforces-Style Problems

2.1 – “Simple Knapsack” (CF-style)

Given n ≤ 10, lists w[i], v[i] and capacity C ≤ 100, compute maximum value allowing fractions. 

Input:
3 50
10 60
20 100
30 120

Output:
240.000000

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main(){
    int n;
    double C;
    cin >> n >> C;
    vector<pair<double,int>> items(n);
    vector<double> w(n), v(n);
    for(int i=0;i<n;i++){
        cin>>w[i]>>v[i];
        items[i] = {v[i]/w[i], i};
    }
    sort(items.begin(), items.end(),
         [&](auto &a, auto &b){ return a.first > b.first; });
    double ans = 0;
    for(auto &it : items){
        int i = it.second;
        if(C >= w[i]){
            C -= w[i];
            ans += v[i];
        } else {
            ans += it.first * C;
            break;
        }
    }
    cout.setf(std::ios::fixed);
    cout.precision(6);
    cout << ans << "\n";
    return 0;
}

2.2 – “Greedy Medal Allocation”

You have n students, each with score s[i] and effort e[i]. You have E effort‐points. Maximize sum of scores by spending effort, fractions allowed. 

Input:
3 5.5
4  10
2  5
6  12

Output:
3.833333

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main(){
    int n; double E;
    cin>>n>>E;
    struct S{ double score, eff, r; };
    vector<S> a(n);
    for(int i=0;i<n;i++){
        cin>>a[i].score>>a[i].eff;
        a[i].r = a[i].score / a[i].eff;
    }
    sort(a.begin(), a.end(),
         [&](auto &A, auto &B){ return A.r > B.r; });
    double total = 0;
    for(auto &x : a){
        if(E >= x.eff){
            E -= x.eff;
            total += x.score;
        } else {
            total += x.r * E;
            break;
        }
    }
    cout.setf(std::ios::fixed);
    cout.precision(6);
    cout<<total<<'\n';
    return 0;
}

3. Two Intermediate Codeforces-Style Problems

3.1 – “Buy Maximum Toys”

You have n toy types, price p[i] and discount weight d[i]. You can buy full toys or fractions of a toy (by weight). Budget B, maximize total discount value. 

Input:
4 20
5 10
8 15
3 6
7 14

Output:
21.000000

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct T{ double disc, wt, r; };
int main(){
    int n; double B;
    cin>>n>>B;
    vector<T> a(n);
    for(int i=0;i<n;i++){
        cin>>a[i].wt>>a[i].disc;
        a[i].r = a[i].disc / a[i].wt;
    }
    sort(a.begin(), a.end(),
         [&](auto &A, auto &B){ return A.r > B.r; });
    double ans=0;
    for(auto &x : a){
        if(B >= x.wt){
            B-=x.wt;
            ans+=x.disc;
        } else {
            ans+=x.r*B;
            break;
        }
    }
    cout.setf(std::ios::fixed);
    cout.precision(6);
    cout<<ans<<'\n';
    return 0;
}

3.2 – “Resource Allocation”

There are m projects, each requires r[j] units of resource and yields g[j] profit. You have R resources, can allocate fractionally. Maximize profit. 

Input:
3 100
20  80
50 200
40 160

Output:
320.000000

#include <iostream>
#include <vector>>
#include <algorithm>>
using namespace std;
struct P{ double res, gain, rg; };
int main(){
    int m; double R;
    cin>>m>>R;
    vector<P> v(m);
    for(int i=0;i<m;i++){
        cin>>v[i].res>>v[i].gain;
        v[i].rg = v[i].gain / v[i].res;
    }
    sort(v.begin(), v.end(),
         [&](auto &A, auto &B){ return A.rg > B.rg; });
    double total=0;
    for(auto &pr : v){
        if(R >= pr.res){
            R -= pr.res;
            total += pr.gain;
        } else {
            total += pr.rg * R;
            break;
        }
    }
    cout.setf(std::ios::fixed);
    cout.precision(6);
    cout<<total<<'\n';
    return 0;
}

4. One Hard Codeforces-Style Problem

4.1 – “Global Resource Distribution”

There are k countries, each produces p[i] units of a commodity at cost c[i] per unit. A global market demand is D, you can buy fractions from any country. Minimize total cost. 

Input:
5 120.0
10  15.0
50  14.0
20  16.0
80  13.5
30  15.5

Output:
1640.000000

#include <iostream>>
#include <vector>>
#include <algorithm>>
using namespace std;
struct C{ double prod, cost, rc; };
int main(){
    int k; double D;
    cin>>k>>D;
    vector<C> a(k);
    for(int i=0;i<k;i++){
        cin>>a[i].prod>>a[i].cost;
        a[i].rc = a[i].cost / a[i].prod;
    }
    // minimize cost per unit → sort by cost ascending
    sort(a.begin(), a.end(),
         [&](auto &A, auto &B){ return (A.cost/A.prod) < (B.cost/B.prod); });
    double totalCost=0;
    for(auto &x : a){
        if(D >= x.prod){
            D -= x.prod;
            totalCost += x.cost;
        } else {
            // fraction of production: cost per unit = x.cost / x.prod
            double unitCost = x.cost / x.prod;
            totalCost += unitCost * D;
            break;
        }
    }
    cout.setf(std::ios::fixed);
    cout.precision(6);
    cout<<totalCost<<'\n';
    return 0;
}

All five examples share the same greedy blueprint:

  • Compute “value per unit” (ratio).
  • Sort by that ratio (descending to maximize, ascending to minimize cost).
  • Take whole items until capacity/demand remains, then take a fraction.
>