AlgoViz
HomeGreedy

Fractional Knapsack

Medium

Take the best value per unit weight first

Problem

Given item values and weights and a bag capacity, maximize value; you may take fractions of an item.

In simple words

Grab items with the highest value-per-kilogram first, taking a fraction of the last one that fits.

The idea

Because items can be split, filling the bag with the highest value-to-weight ratio available is always optimal — the last item is simply taken partially. That is the key difference from 0/1 knapsack, where splitting is banned and greedy fails.

The trick

  • Sort by value/weight descending and take greedily.
  • The final item may be taken fractionally to fill the remaining capacity.
  • 0/1 knapsack needs DP — this greedy is wrong there.

This one walks through the worked example rather than tracing the algorithm frame by frame — a full walkthrough is still to be drawn. The code and the idea below are the real solution.

60
100
120
0
1
2

Step 1 of 2. Here's the example — val=[60,100,120], wt=[10,20,30], W=50 Values: 60, 100, 120.

1/2
Optimal
timeO(n log n)spaceO(1)
1sort items by value/weight desc2for each item:3  if fits: take fully; W -= wt4  else: take W/wt fraction; break

Input

array
[60, 100, 120]

Output

answer
—

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Examples

Example 1

Input:
items(w,v) = [(10,60),(20,100),(30,120)], cap = 50
Output:
240.0
Explanation:
Take the best value-per-kg first → 240.

Example 2

Input:
items(w,v) = [(10,60)], cap = 5
Output:
30.0
Explanation:
Take half of the only item → 30.

Example 3

Input:
items(w,v) = [(5,50),(5,50)], cap = 10
Output:
100.0
Explanation:
Both fit → 100.

Practice this problem:GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.