Fractional Knapsack

Maximize total value by taking items greedily by highest value-to-weight ratio. Greedy works here because fractions are allowed, making the ratio choice provably optimal.

Algorithm Steps

Compute ratio value/weight for each item.
Sort by decreasing ratio.
Take fully while capacity allows; otherwise take fraction of next item.

Capacity

Speed (ms)

Item Av=60, w=10, r=6

Taken: 0%

Item Bv=100, w=20, r=5

Taken: 0%

Item Cv=120, w=30, r=4

Taken: 0%

Capacity usage

Bars indicate fraction of each item added.

Pseudocode

1procedure FRACTIONAL_KNAPSACK(items, W)
2  sort items by value/weight in decreasing order
3  total ← 0
4  for each item in items do
5    if W = 0 then break
6    if item.weight ≤ W then
7      take 100% of item; W ← W − item.weight; total ← total + item.value
8    else
9      take fraction = W / item.weight; total ← total + item.value * fraction; W ← 0
10    end if
11  end for
12  return total
13end procedure

Practice Problems

Use Cases

Bandwidth allocation where partial usage is allowed.
Cutting-stock and blending problems with fractional items.
Greedy baseline for 0/1 knapsack (contrast case).

Back to Activity Selection Next: Huffman Coding