Fractional Knapsack

Highest value-per-weight first — fractions make greedy provably optimal

time O(n log n)space O(n)

Because items can be split, there's no risk of 'wasting' leftover capacity the way 0/1 knapsack can — so greedily taking the item with the best value-per-unit-weight first is always at least as good as any other order, and topping off the last item with a fraction uses every bit of capacity. This is what makes fractional knapsack solvable greedily while its 0/1 cousin needs full dynamic programming.

Details

Animated on: items (value,weight) = (60,10), (100,20), (120,30), capacity = 50 — maximize value, fractions of an item allowed.

Problem:Fractional KnapsackEasy

Highest value-per-weight first — fractions make greedy provably optimal

step 1 / 5

(v60,w10)

[0]

(v100,w20)

[1]

(v120,w30)

[2]

Sort items by value/weight ratio, highest first: (v60,w10)=6.00, (v100,w20)=5.00, (v120,w30)=4.00. Fractions are allowed, so always grabbing the best ratio first can never be beaten.

Pseudocode

1FUNCTION fractionalKnapsack(items, capacity):
2  sort items by value/weight ratio, highest first
3  totalValue = 0
4  FOR each item in items:
5    IF item weight <= remaining capacity:
6      take it fully; add item value to totalValue
7    ELSE:
8      take a remaining/weight fraction; add fraction * value to totalValue
9  RETURN totalValue

← / → step · space play · Home restart

Every step in words

Show all 5 steps

Sort items by value/weight ratio, highest first: (v60,w10)=6.00, (v100,w20)=5.00, (v120,w30)=4.00. Fractions are allowed, so always grabbing the best ratio first can never be beaten.
(v60,w10) fits entirely (weight 10 <= remaining 50). Take all of it: +60 value. Remaining capacity = 40.
(v100,w20) fits entirely (weight 20 <= remaining 40). Take all of it: +100 value. Remaining capacity = 20.
(v120,w30): only 20 capacity left, item weighs 30. Take a fraction (20/30 = 0.67): +80.00 value.
Capacity 50 fully used. Maximum total value = 240.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Fractional Knapsack in the editor All Greedy problems Back to roadmap