14.7 Fractional Knapsack

The fractional knapsack problem is one of the clearest examples of a greedy algorithm producing an optimal solution. Unlike many optimization problems where local decisions can lead to poor global outcomes, fractional knapsack possesses a structure that makes the greedy choice immediately obvious once the correct perspective is adopted.

The problem is important for two reasons. First, it demonstrates a powerful exchange argument. Second, it provides a useful contrast with the 0/1 knapsack problem, where a nearly identical problem statement requires dynamic programming rather than a greedy strategy.

The difference between the two problems is only a single word:

fractional

That one change completely alters the mathematical structure of the problem.

Problem

A knapsack has capacity:

$$ W $$

There are (n) items.

Each item has:

• Weight (w_i)
• Value (v_i)

Unlike the 0/1 knapsack problem, an item may be divided into arbitrary fractions.

Goal:

Maximize total value without exceeding capacity.

Example

Capacity:

$$ W = 50 $$

Items:

Item	Weight	Value
A	10	60
B	20	100
C	30	120

At first glance, many choices appear possible.

A better view emerges when we compute value density.

Value Density

Define:

$$ d_i = \frac{v_i}{w_i} $$

For the example:

Item	Weight	Value	Density
A	10	60	6
B	20	100	5
C	30	120	4

Density measures value gained per unit weight.

Higher density means greater efficiency.

Key Greedy Observation

Suppose one kilogram of capacity remains.

Would we rather fill it with:

• An item producing value 6 per kilogram?
• An item producing value 4 per kilogram?

The answer is obvious.

Every unit of capacity should be allocated to the highest-density item available.

This immediately suggests the greedy rule:

Always take as much as possible from the item with highest value density.

Greedy Algorithm

Step 1

Compute:

$$ \frac{v_i}{w_i} $$

for every item.

Step 2

Sort items by decreasing density.

Step 3

Process items in that order.

For each item:

• Take the whole item if possible.
• Otherwise take the remaining fraction that fits.

Continue until capacity is exhausted.

Example Walkthrough

Sorted order:

Item	Density
A	6
B	5
C	4

Take A

Weight:

$$ 10 $$

Value:

$$ 60 $$

Remaining capacity:

$$ 40 $$

Take B

Weight:

$$ 20 $$

Value:

$$ 100 $$

Remaining capacity:

$$ 20 $$

Take Fraction of C

C weighs:

$$ 30 $$

Only:

$$ 20 $$

capacity remains.

Take:

$$ \frac{20}{30} = \frac{2}{3} $$

of C.

Value obtained:

$$ 120 \times \frac{2}{3} = 80 $$

Total Value

$$ 60 + 100 + 80 = 240 $$

Final solution:

Item	Fraction Taken
A	1
B	1
C	2/3

Total value:

$$ 240 $$

This is optimal.

Geometric Interpretation

Imagine capacity as a horizontal line.

Each item contributes value at a constant rate equal to its density.

Density 6
Density 5
Density 4

To maximize total value, capacity should always be allocated to the steepest available slope first.

The greedy strategy becomes almost inevitable.

Why the Greedy Choice Works

Suppose an optimal solution violates the greedy rule.

There exists:

• A higher-density item partially unused.
• A lower-density item partially used.

Let:

$$ d_h > d_l $$

Transfer a small amount of weight:

$$ \Delta $$

from the lower-density item to the higher-density item.

Value change:

$$ (d_h - d_l)\Delta $$

Since:

$$ d_h > d_l $$

the value strictly increases.

The original solution therefore cannot be optimal.

This contradiction proves:

Every optimal solution must fully utilize higher-density items before lower-density items.

The greedy choice is safe.

Exchange Argument

Suppose:

Item	Density
A	6
B	4

An alleged optimal solution uses:

5 units of B

while leaving:

5 units of A

unused.

Exchange those 5 units.

Value gain:

$$ (6-4)\times5 = 10 $$

The objective improves.

The original solution was not optimal.

Repeated exchanges eventually transform any optimal solution into the greedy solution.

This is a classic exchange argument.

Proof of Optimality

Greedy Choice Property

The highest-density item must be used as much as possible.

Optimal Substructure

After taking the highest-density item, the remaining capacity forms a smaller fractional knapsack problem.

Recursive Reduction

The same reasoning applies repeatedly.

Therefore the greedy algorithm constructs an optimal solution.

Implementation

Go

type Item struct {
	Weight float64
	Value  float64
}

Sorting by density:

sort.Slice(items, func(i, j int) bool {
	return items[i].Value/items[i].Weight >
		items[j].Value/items[j].Weight
})

Selection loop:

remaining := capacity
total := 0.0

for _, item := range items {
	if remaining == 0 {
		break
	}

	if item.Weight <= remaining {
		total += item.Value
		remaining -= item.Weight
	} else {
		fraction := remaining / item.Weight
		total += fraction * item.Value
		remaining = 0
	}
}

Complexity Analysis

Sorting:

$$ O(n\log n) $$

Selection pass:

$$ O(n) $$

Total:

$$ O(n\log n) $$

Space:

$$ O(1) $$

excluding sorting overhead.

Why 0/1 Knapsack Is Different

Now remove the word "fractional".

Items can no longer be split.

Example:

Item	Weight	Value
A	10	60
B	20	100
C	30	120

Capacity:

$$ 50 $$

Density order:

A -> B -> C

Greedy result:

$$ 60 + 100 = 160 $$

Optimal result:

$$ 100 + 120 = 220 $$

The greedy algorithm fails.

The exchange argument collapses because fractions cannot be transferred.

This demonstrates how a small modeling change can completely alter algorithm design.

Real-World Applications

Cargo Loading

Some commodities can be divided freely.

Examples:

• Grain
• Oil
• Sand
• Chemicals

Bandwidth Allocation

Network capacity can often be divided continuously.

Investment Allocation

Capital may be distributed fractionally among assets.

Resource Scheduling

Computational resources may be allocated proportionally.

In these situations the fractional assumption is realistic.

Common Mistakes

Sorting by Value

High-value items may have poor density.

Sorting by Weight

Light items may contribute little value.

Forgetting Fractions

The final item is often only partially selected.

Applying the Same Logic to 0/1 Knapsack

This is the most common error.

The proof relies completely on divisibility.

Without divisibility, the greedy argument fails.

Relationship to Previous Sections

Activity selection chooses:

Earliest finish time

Huffman coding chooses:

Lowest frequencies

Fractional knapsack chooses:

Highest value density

The exact criterion changes, but the proof pattern remains the same:

1. Identify a locally optimal choice.
2. Show any optimal solution can be transformed to include it.
3. Reduce the problem size.
4. Repeat.

This pattern defines the essence of greedy algorithm design.

Takeaway

Fractional knapsack is a canonical greedy optimization problem. By sorting items according to value density and always taking as much as possible from the highest-density item, an optimal solution can be constructed in (O(n\log n)) time. The correctness proof follows from an exchange argument showing that any solution allocating capacity to a lower-density item before a higher-density one can be improved. The problem also provides a valuable lesson: small changes in problem constraints can completely change which algorithmic techniques apply, as demonstrated by the dramatic contrast with the 0/1 knapsack problem.