Fractional Knapsack
Maximize value under a weight cap when items are divisible. Sort by value-to-weight ratio and fill greedily — the last item is taken in fraction.
- Category
- Greedy
- Time complexity
- O(n log n)
- Space complexity
- O(1)
Pseudocode
sort items by value/weight desc take whole items while they fit take a fraction of the next stop when full
Reference implementation
items.sort(key=lambda i: -i.v/i.w)
for it in items:
if cap >= it.w: take_all(it)
else: take_fraction(it, cap/it.w); break