Pattern visualizer

Fractional Knapsack

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. Animated on: items (value,weight) = (60,10), (100,20), (120,30), capacity = 50 — maximize value, fractions of an item allowed..

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

time O(n log n)space O(n)step 1 / 5

(v60,w10)

[0]

(v100,w20)

[1]

(v120,w30)

[2]

line 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

Where to practice Greedy

Practice Greedy problems All Greedy problems Back to roadmap