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.

How to spot this pattern

Fractions are what make greedy legal here. Because you may take part of an item, filling the bag with the best value-per-unit-weight first is provably optimal — there's never a reason to leave a denser item behind. The instant items become indivisible (0/1 knapsack), that argument collapses and you need DP. Spotting whether splitting is allowed decides the entire approach.

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

▶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

Common pitfalls

Sorting by value instead of value-to-weight ratio

✗ Wrong

items.sort(key=lambda x: x[0], reverse=True)

✓ Right

items.sort(key=lambda x: x[0] / x[1], reverse=True)

A high-value item can be so heavy that it crowds out several lighter items worth more in total. What the bag is really spending is capacity, so the quantity to maximise is value per unit of weight.

Skipping an item that doesn't fit whole

✗ Wrong

if W >= w:
    total += v; W -= w
else:
    continue

✓ Right

else:
    total += v * W / w
    break

This is the difference between the fractional problem and 0/1. Once an item doesn't fit entirely, you take the portion that does — and since the bag is then exactly full, no later item can be added, so you stop.

Integer division on the partial take

✗ Wrong

total += v * W // w

✓ Right

total += v * W / w

The whole point of the fractional variant is that the answer is generally not an integer. Floor division silently discards the remainder of the last, partially-taken item.

06

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.

07

Complexity

Time

O(n log n)

Space

O(1)

Sort then single pass.