GreedyGreedy

Fractional Knapsack

Maximize value in a capacity-limited knapsack when items can be taken in fractions: take items in decreasing value-per-weight order.

Learn Fractional Knapsack →
a
60
0
100
1
120
2
item
A
0
B
1
C
2
weight
10
0
20
1
30
2
1/133 items and a knapsack of capacity 50. Each item may be cut, so the only thing that matters about an item is how much value it packs per unit of weight — the value alone is misleading, because a large value attached to a large weight can crowd out two denser items.
Item being consideredTaken wholeTaken as a fractionLeft behind (no capacity)Where 0/1 greedy goes wrong
PseudocodeLearn Fractional Knapsack →
1sort items by value / weight, descending
2total = 0
3for each item (w, v):
4  if w <= capacity:                 # the whole item fits
5    capacity -= w; total += v
6  else:                             # take only the fraction that fits
7    total += v * (capacity / w); capacity = 0; break
8return total
Variables
capacity50
items3
totalWeight60
value0
Complexity
avg O(n log n)
worst O(n log n)
space O(1)
Speed