The Fractional Knapsack problem allows taking fractions of items unlike the 0/1 variant. The greedy solution is optimal: sort items by value/weight ratio descending, and greedily fill the knapsack with as much of the highest-ratio item as possible, then the next, and so on. O(n log n) due to sorting.
double fractionalKnapsack(vector<int>& w, vector<int>& v, int W) {
int n=w.size();
vector<pair<double,int>> items(n);
for(int i=0;i<n;i++) items[i]={v[i]/(double)w[i],i};
sort(items.rbegin(),items.rend());
double total=0; int rem=W;
for(auto[ratio,i]:items){
if(rem==0)break;
int take=min(w[i],rem);
total+=take*ratio; rem-=take;
}
return total;
}Sort items by value/weight ratio in descending order. Take as much as possible of the highest-ratio item. This maximizes value per unit of capacity used.
Unlike 0/1 Knapsack (where DP is needed), fractional knapsack allows greedy because partial items are allowed. There is no combinatorial choice — just fill optimally ratio by ratio.
Fractional knapsack is O(n log n) with greedy. 0/1 Knapsack requires O(nW) DP because you cannot take fractions. The fractional solution is always >= the 0/1 solution for the same instance.
Quiz coming soon for this algorithm.