GeeksforGeeks Medium

Fractional Knapsack

Items have value and weight; capacity is W. You may take fractions of items. Maximize total value.

greedysorting

02

Intuition

💡

Because items are divisible, there's no packing subtlety: every kilogram of capacity should carry the densest value available. Sort by value/weight and pour items in, topping off with a fraction of the last one.

03

Approach

1

Sort by value density

value ÷ weight is the worth of one unit of capacity spent on that item.

2

Take greedily

Take whole items while they fit; when the next doesn't, take exactly the fraction that fills the sack and stop.

3

Why fractions make greedy exact

With divisibility, swapping any low-density mass for unused high-density mass strictly improves — an optimum must follow density order. (The 0/1 version breaks this and needs DP.)

04

Solution & live demo

python

▶1def fractional_knapsack(items, W):   # items: [(value, weight)]
▶2    items.sort(key=lambda x: x[0] / x[1], reverse=True)
▶3    total = 0.0
▶4    for v, w in items:
▶5        if W >= w:
▶6            total += v; W -= w
▶7        else:
▶8            total += v * W / w
▶9            break
▶10    return total

05

Edge cases

Capacity exhausts mid-item

Take remaining/weight of it — the only fractional take, always the last.

Capacity exceeds total weight

Everything fits; answer is the total value.

06

Complexity

Time

O(n log n)

Space

O(1)

Sort then single pass.