Fractional Knapsack

Fractional knapsack maximizes total value under a weight limit when any fraction of an item may be taken. A high value-per-weight ratio is the correct local priority because divisible weight can be exchanged in equal amounts. This assumption separates the problem from 0/1 knapsack, where an item is indivisible and the same greedy ordering can be wrong.

Prerequisites: Sorting; cross multiplication; exchange arguments; floating-point output.

Build the idea

1. Specify divisible items

   Each item has strictly positive weight w and nonnegative value v; taking fraction f∈[0,1] contributes fw weight and fv value. Capacity need not be filled if no valuable material remains. Sort by decreasing v/w. The program reads integer weights and values, but allows a fractional final item through a floating value calculation.

2. Compare ratios safely

   Instead of dividing in the comparator, compare vA·wB against vB·wA. Integer products remain exact because each input weight/value is at most 10^9, so products fit within 10^18. Break equal-ratio ties by ID for strict deterministic ordering. This product bound would need revision for larger inputs; an epsilon comparator is not a safe substitute for std::sort ordering.

   $$\mathrm{valueAdded}=\mathrm{takenWeight}·\mathrm{itemValue}/\mathrm{itemWeight}$$

3. Correctness proof: exchange equal weight

   Suppose a feasible solution uses some lower-ratio material while leaving higher-ratio material available. Replace a small equal weight δ of the former by the latter, up to the capacity of either item. Weight is unchanged and value rises by δ(rHigh−rLow)≥0. Repeating exchanges yields a solution that fully takes higher ratios before lower ones, with at most one partially used item after ties are ordered. This is exactly the greedy scan.

4. Trace the sample

   Capacity 50 and items (weight,value)=(10,60),(20,100),(30,120) have ratios 6,5,4. Take the first two fully, using weight 30 and value 160. Twenty capacity remains, so take two thirds of the third item for value 80. Total is 240. The code stores amount, the taken weight, and adds amount·value/weight using long double.

5. Show the indivisible failure

   For the same instance, 0/1 ratio-first takes the first two items for value 160 and cannot fit the third. The better indivisible choice is items two and three, value 220. The exchange proof fails because replacing a small equal weight is illegal for indivisible items. A large-looking numerical answer is not evidence that the model allows those fractions.

This is a complete program. Compile with C++17 and enter the input described below.

#include<iostream>
#include<vector>
#include<algorithm>
#include<iomanip>
struct Item{
    long long weight,value;
    int id;
};
int main(){
    int n;
    long long capacity;
    std::cin>>n>>capacity;
    std::vector<Item>a(n);
    for(int i=0;i<n;++i){
        std::cin>>a[i].weight>>a[i].value;
        a[i].id=i+1;
    }
    std::sort(a.begin(),a.end(),[](Item x,Item y){
        long long left=x.value*y.weight,right=y.value*x.weight;
        return left!=right?left>right:x.id<y.id;
    });
    long double total=0;
    for(Item x:a){
        long long amount=std::min(capacity,x.weight);
        total+=(long double)amount*x.value/x.weight;
        capacity-=amount;
        if(capacity==0){
            break;
        }
    } // amount may be a fraction of the item's weight.
    std::cout<<std::fixed<<std::setprecision(6)<<total<<'\n';
}

Complexity analysis

O(n log n) sorting and O(n) scan, O(n) item storage. Ratio comparison products fit long long under the explicit 10^9 bounds; total value is at most 10^14. Fractional output is approximate, not an exact rational certificate.

Example input and output

Read n capacity (0≤n≤100000, 0≤capacity≤10^12), then n positive weights and nonnegative values, each at most 10^9. Item fractions are allowed. Print the approximate maximum value to six decimals.

Input

3 50
10 60
20 100
30 120

Output

240.000000

Taking 10+20+20 units of weight yields 60+100+80 value.

Practical applications

Use when resources are genuinely divisible: material, time or continuous allocations with constant per-unit value. Use 0/1 knapsack DP or another discrete method when whole-item choices are required. Fractional knapsack can also provide an upper bound inside branch-and-bound.

Check your understanding

Which assumption makes the equal-weight exchange legal?

Put it into practice

Compare fractional and 0/1 optima for the sample.