Fractional Knapsack — When Greedy Achieves Optimality

Consider two versions of the same challenge:

Scenario A (Discrete): You're buying gold bars to invest in. Each bar weighs exactly 1 kilogram and costs a specific price. You cannot buy half a bar — it's all or nothing.

Scenario B (Fractional): You're buying gold dust by weight. You can purchase exactly as much as you want — 1kg, 0.7kg, or even 0.001kg.

These two scenarios have fundamentally different optimization characteristics. The first requires combinatorial reasoning — which discrete bars maximize value? The second admits a beautifully simple solution: buy the cheapest gold per gram first, then the next cheapest, until your budget is exhausted.

The Fractional Knapsack problem falls into Scenario B. The ability to take fractions of items completely transforms the mathematical structure of the problem, enabling a greedy algorithm that is both simple and provably optimal.

In the Fractional Knapsack problem, we associate with each item i a decision variable xᵢ representing the fraction of that item we take.

Formal Definition:

For item i with weight wᵢ and value vᵢ:

• xᵢ ∈ [0, 1] is the fraction of item i selected
• xᵢ = 0: We take none of item i
• xᵢ = 1: We take all of item i
• 0 < xᵢ < 1: We take a partial amount of item i

Weight and Value of Fractional Selection:

• Weight consumed by taking fraction xᵢ of item i: xᵢ · wᵢ
• Value gained by taking fraction xᵢ of item i: xᵢ · vᵢ

This linear scaling is crucial. If you take half of an item (xᵢ = 0.5), you consume half its weight and gain half its value. The proportionality is exact — there are no economies or diseconomies of scale.

Computing Fractional Contributions:

Let's make this concrete with an example item:

• Item X: weight = 10 kg, value = $200

What happens at different fractions?

Key Observation: The value density remains constant regardless of the fraction taken. This invariance is why the greedy approach works — each incremental unit of this item has the same 'return rate'.

The ability to take fractions fundamentally changes the optimization landscape. To understand why, we must examine what goes wrong in the discrete (0/1) case and how fractionality solves it.

The Discrete Problem — Wasted Capacity:

Consider 0/1 Knapsack with capacity W = 10 and two items:

• Item A: weight = 7, value = 35 (density = 5)
• Item B: weight = 5, value = 20 (density = 4)

Greedy by density selects A first (density 5 > 4). After taking A, remaining capacity = 3. Item B needs 5, so it can't fit. Greedy gets value = 35, with 3 units of wasted capacity.

But the optimal 0/1 solution might be to skip A and take only B? No — value 20 < 35. Actually, greedy wins here. But consider:

• Item A: weight = 6, value = 30 (density = 5)
• Item B: weight = 5, value = 24 (density = 4.8)
• Capacity = 10

Greedy takes A (value 30), remaining capacity = 4, B doesn't fit. Total = 30. Optimal: Take B only? No, 24 < 30. But what if there's a third item that fits in 4?

With more items, the discrete case can have greedy failures. The point: discrete selection creates 'leftovers' that may be suboptimally filled.

The Fractional Solution — Perfect Packing:

With the same items (A: w=6, v=30; B: w=5, v=24; W=10):

Greedy by density:

1. Take all of A: weight = 6, value = 30, remaining = 4
2. Remaining capacity = 4. B weighs 5. Take 4/5 = 0.8 of B.
3. Value from B fraction: 0.8 × 24 = 19.2

Total: 30 + 19.2 = 49.2

Every unit of the 10kg capacity is filled. The last 4kg is filled with the highest-density available material (which happens to be part of B).

The Core Insight:

Fractionality ensures that each unit of capacity is allocated to the currently-highest density material. Since density represents value per unit weight, this means each marginal unit of capacity is earning the best possible return. No reallocation can improve the solution — it is already optimal.

This is why greedy works: every local decision (take highest density available) is also globally optimal when fractions are allowed.

Let's formalize the greedy algorithm for Fractional Knapsack. The procedure is elegant and efficient.

Algorithm: Fractional Knapsack Greedy

Input: n items with (wᵢ, vᵢ), capacity W
Output: fractions x₁, x₂, ..., xₙ and total value

1. Compute value density ρᵢ = vᵢ/wᵢ for each item i
2. Sort items in decreasing order of ρᵢ
3. Initialize: remaining_capacity = W, total_value = 0
4. For each item i in sorted order:
   a. If wᵢ ≤ remaining_capacity:
      - Take all of item i: xᵢ = 1
      - remaining_capacity -= wᵢ
      - total_value += vᵢ
   b. Else if remaining_capacity > 0:
      - Take fraction: xᵢ = remaining_capacity / wᵢ
      - total_value += xᵢ * vᵢ
      - remaining_capacity = 0
      - Break (knapsack is full)
   c. Else:
      - xᵢ = 0 (no room left)
5. Return x₁...xₙ, total_value

Step-by-Step Trace — Example:

Items: A (w=10, v=60, ρ=6), B (w=20, v=100, ρ=5), C (w=30, v=120, ρ=4) Capacity W = 50

After Sorting by Density: A, B, C

Iteration 1 (Item A):

• ρ_A = 6 (highest)
• w_A = 10 ≤ 50 (remaining) ✓
• Take all: x_A = 1, value += 60
• remaining = 50 - 10 = 40

Iteration 2 (Item B):

• ρ_B = 5 (next highest)
• w_B = 20 ≤ 40 (remaining) ✓
• Take all: x_B = 1, value += 100
• remaining = 40 - 20 = 20

Iteration 3 (Item C):

• ρ_C = 4 (next)
• w_C = 30 > 20 (remaining) ✗
• Take fraction: x_C = 20/30 = 2/3 ≈ 0.667
• value += (2/3) × 120 = 80
• remaining = 0

Final Solution:

• x_A = 1, x_B = 1, x_C = 2/3
• Total value = 60 + 100 + 80 = 240
• Total weight = 10 + 20 + 20 = 50 (exactly filled)

When we reach an item that doesn't fully fit, we must compute the precise fraction to take. This calculation is straightforward but worth examining carefully.

The Fractional Fill Calculation:

Given:

• Item i with weight wᵢ and value vᵢ
• Remaining capacity: R (where R < wᵢ)

The fraction of item i to take is:

xᵢ = R / wᵢ

The value gained is:

xᵢ × vᵢ = (R / wᵢ) × vᵢ = R × (vᵢ / wᵢ) = R × ρᵢ

This last form is illuminating: the value gained equals the remaining capacity times the item's value density. We're essentially 'spending' R units of capacity at the item's exchange rate.

Numerical Precision Considerations:

In practice, fractional calculations may involve floating-point numbers. Consider:

• Item: w = 7, v = 100
• Remaining capacity: R = 5
• Fraction: x = 5/7 ≈ 0.714285...
• Value: 5/7 × 100 ≈ 71.43

Implementation Tips:

1. Use floating-point arithmetic: Results are often non-integer
2. Consider precision: If exact rational answers are needed, use fraction libraries or track numerator/denominator separately
3. Round appropriately for output: Display with reasonable decimal places
4. Be aware of cumulative errors: In problems with many fractional operations, errors can accumulate

Alternative Perspective — Density Interpretation:

Another way to think about the fractional fill:

• We have R units of capacity to fill
• The current item offers ρ value per unit weight
• Filling R units yields R × ρ value

This matches exactly with looking at density as an 'exchange rate' between capacity and value.

Not all problems permit fractional selection. Understanding when fractions are meaningful helps identify problems that fit the Fractional Knapsack model.

Characteristics of Fractional Problems:

Examples Where Fractions Are Valid:

The Spectrum of Divisibility:

Real problems often fall on a spectrum:

• Perfectly divisible: Money, time, bulk commodities → Fractional Knapsack
• Approximately divisible: Large batch sizes where fractional loss is negligible → Often modeled as Fractional
• Quantized but small units: Can approximate as continuous if unit size << capacity
• Fundamentally discrete: Cars, servers, discrete licenses → 0/1 Knapsack

Modeling Decision:

When facing a real problem, ask: "If I take 73.2% of this item, does that make sense operationally?" If yes, model as Fractional Knapsack. If no, model as 0/1.

To truly understand why the greedy algorithm works, we must identify the invariant — a property that holds after each step and guarantees eventual optimality.

The Greedy Knapsack Invariant:

At every step, the current partial solution is optimal for the capacity used so far.

Intuitive Argument:

Consider the first unit of capacity. Which item should 'occupy' it? Since we can take fractions, we should allocate this unit to the item with highest value density — say, item A with ρ_A = 10.

Now consider the second unit. It should go to the highest-density item available. If A still has supply, it stays at A. If A is exhausted, move to the second-highest density item.

This reasoning extends to every unit of capacity. Each incremental allocation goes to the best available 'rate of return.' Since fractions allow perfect subdivision, every unit of capacity earns the maximum possible value — no reallocation can improve the outcome.

Why Discrete Knapsack Breaks This:

In 0/1 Knapsack, you can't take items 'one gram at a time.' You must commit to entire items. The first gram of a large item commits you to potentially many grams you might later regret.

Example:

• Item A: w=100, v=200, ρ=2
• Item B: w=50, v=90, ρ=1.8
• Item C: w=50, v=85, ρ=1.7
• Capacity: 100

Greedy takes A (ρ=2): weight=100, value=200. Done.

Optimal 0/1: Take B+C: weight=100, value=175. Wait, that's worse!

Hmm, actually greedy wins here. Let me construct a better counterexample:

• Item A: w=50, v=100, ρ=2
• Item B: w=30, v=55, ρ=1.83
• Item C: w=30, v=54, ρ=1.8
• Capacity: 60

Greedy takes A (ρ=2): weight=50, value=100. Remaining=10. Nothing fits. Optimal 0/1: Take B+C: weight=60, value=109.

Greedy: 100 vs. Optimal: 109. The discrete constraint causes failures.

A powerful way to understand Fractional Knapsack is to visualize it as filling a container with liquids of varying densities.

The Liquid Analogy:

Imagine:

• The knapsack is a tank that can hold W liters
• Each item is a drum of colored liquid with a specific volume (weight) and worth (value)
• The 'density' of each liquid is its value per liter
• We can pour any amount from any drum

Optimal Strategy:

1. Line up drums in order of liquid density (value per liter)
2. Pour from the densest drum until empty or tank is full
3. Move to next densest drum
4. Continue until tank is exactly full

The tank ends up stratified: the densest liquid at bottom, less dense liquid above, with a precise fractional pour from one drum to top off.

Graphical Interpretation:

Plot items on a graph:

• X-axis: Cumulative weight
• Y-axis: Value density (ρ = v/w)

Items become horizontal bars at their density level, with width equal to their weight. To find total value for capacity W:

1. Draw a vertical line at x = W
2. Sum the 'area' of each bar up to that line
3. If the line cuts through a bar, that item is taken fractionally

The area under this 'staircase' curve (sorted by decreasing density) represents total value. Any other ordering would have less area for the same width — proving greedy optimality graphically.

We've thoroughly explored what it means to take fractions in the Fractional Knapsack problem and why this capability is the key to greedy optimality.

What's Next:

Now that we understand fractional selection, the next page formally presents the greedy by value-to-weight ratio algorithm. We'll implement it step by step, analyze its time complexity, and provide a rigorous proof of its optimality using the exchange argument.