Fractional Knapsack Problem

You're robbing a jewelry store. Your backpack holds 50 kg. You have:

• Gold bars: 60 kg total, worth $6000 ($100/kg)
• Diamonds: 20 kg total, worth $4000 ($200/kg)
• Silver: 30 kg total, worth $1500 ($50/kg)

You can break items and take fractions. What do you take?

Naive approach: take the most valuable total. Gold is worth $6000. But it weighs 60 kg—won't fit.

Better: look at value per kilogram. Diamonds are $200/kg, gold is $100/kg, silver is $50/kg.

Greedy strategy: take items with the highest value per kilogram first.

Capacity: 50 kg

1. Take all diamonds: 20 kg, $4000. Remaining: 30 kg
2. Take gold: need 30 kg, have 60 kg. Take 30/60 = 50% of it.
   Value: 30 kg × $100/kg = $3000. Remaining: 0 kg

Total: $4000 + $3000 = $7000

That's optimal. If you took gold first (only 50 kg of it), you'd get $5000. If you took silver, even worse.

The Algorithm

def fractional_knapsack(items, capacity):
    # Calculate value/weight ratio for each item
    items_with_ratio = []
    for value, weight in items:
        ratio = value / weight
        items_with_ratio.append((ratio, value, weight))
    
    # Sort by ratio, descending
    items_with_ratio.sort(reverse=True)
    
    total_value = 0
    remaining = capacity
    
    for ratio, value, weight in items_with_ratio:
        if weight <= remaining:
            # Take the whole item
            total_value += value
            remaining -= weight
        else:
            # Take a fraction
            fraction = remaining / weight
            total_value += value * fraction
            remaining = 0
            break  # Knapsack full
    
    return total_value

For our jewelry store:

Items: [(6000, 60), (4000, 20), (1500, 30)]
Ratios: [100, 200, 50]

With ratios: [(200, 4000, 20), (100, 6000, 60), (50, 1500, 30)]

Capacity: 50

Iteration 1: ratio=200, value=4000, weight=20
  20 <= 50, take whole item
  total_value = 4000, remaining = 30

Iteration 2: ratio=100, value=6000, weight=60
  60 > 30, take fraction
  fraction = 30/60 = 0.5
  total_value = 4000 + 6000×0.5 = 7000
  remaining = 0
  
Return 7000

Time complexity: O(n log n) for sorting + O(n) for greedy loop = O(n log n).

Why Greedy Works Here

The value/weight ratio tells you how "efficient" an item is. Taking the most efficient items first maximizes total value.

Can we do better by taking less efficient items? No. Suppose we skip a high-ratio item to take a low-ratio one. We'd get less value per unit weight, reducing the total. Swapping back to the high-ratio item always improves the solution.

This is the greedy choice property: the locally optimal choice (highest ratio) leads to a globally optimal solution.

A More Complex Example

Items:

Item 1: value=60, weight=10 → ratio=6.0
Item 2: value=100, weight=20 → ratio=5.0
Item 3: value=120, weight=30 → ratio=4.0

Capacity: 50

Sorted by ratio: Item 1 (6.0), Item 2 (5.0), Item 3 (4.0)

Take Item 1: weight=10, value=60. Remaining: 40
Take Item 2: weight=20, value=100. Remaining: 20
Take Item 3: need 30, have 20. Take 20/30.
  value = 120 × (20/30) = 80. Remaining: 0

Total: 60 + 100 + 80 = 240

If we took them in a different order:

• Item 3 first: 30 kg, $120. Then Item 2: 20 kg, $100. Total: $220 (worse)
• Item 2 first: 20 kg, $100. Then Item 1: 10 kg, $60. Then Item 3: 20 kg of it, $80. Total: $240 (same as greedy)

Actually, the second approach also gave $240. Let me recalculate:

• Item 2 (20 kg, $100), Item 1 (10 kg, $60), Item 3 (20/30, $80) = $240

Both orderings that prioritize high ratios give the same result. That's expected—multiple optimal solutions can exist, but greedy finds one of them.

Fractional vs 0/1 Knapsack

Fractional: Can take fractions. Greedy works.

0/1: Must take whole items. Greedy fails.

For the same items with capacity 50:

• Greedy (by ratio): Item 1 (10 kg, $60), Item 2 (20 kg, $100). Can't fit Item 3. Total: $160
• Optimal: Item 2 (20 kg, $100), Item 3 (30 kg, $120). Total: $220

Greedy gives $160, but optimal is $220. For 0/1 knapsack, you need dynamic programming.

Why does greedy fail for 0/1? Because you can't take fractions. The greedy choice might leave unused capacity that can't be filled efficiently. DP considers all combinations to find the true optimum.

Proof of Optimality

Suppose there's an optimal solution that doesn't follow greedy's order. It must skip some high-ratio item A for a lower-ratio item B.

Swap them: replace some of B with A. Since A has a higher ratio, you get more value for the same weight (or more value with less weight, leaving room for more items).

This swap improves or maintains the solution, contradicting the assumption that the non-greedy solution was optimal.

Therefore, greedy is optimal for fractional knapsack.

Practical Applications

Resource allocation: Allocating limited budget across projects with different ROI (return on investment). Prioritize high ROI projects.

Network bandwidth: Allocating bandwidth to data streams. Prioritize streams with highest priority/bandwidth ratio.

Investment portfolio: With divisible assets, invest in highest return/risk ratio first.

Loading cargo: Shipping containers with weight limits. Load highest value/weight items first.

Implementation Details

Edge cases:

• Empty items list: return 0
• Zero capacity: return 0
• All items fit: take all, no fractions needed

Floating point precision: When calculating ratios and fractions, be careful with floating-point arithmetic. For exact results, use integer arithmetic where possible.

Ties in ratio: If two items have the same ratio, the order doesn't matter—either can come first without affecting optimality.

The Key Insight

Fractional knapsack is greedy-friendly because you can take partial items. This flexibility means the locally optimal choice (highest ratio) doesn't block better global solutions—you can always adjust by taking more or less of subsequent items.

For 0/1 knapsack, you can't adjust. Taking an item commits you, potentially blocking combinations that would be better. That's why you need DP.

Recognizing when a problem allows "fractional" choices vs "all-or-nothing" choices tells you whether greedy will work or if you need DP.

Comparison Table

Fractional knapsack is the easier problem. Master it, understand why greedy works, and you'll appreciate why 0/1 knapsack needs something more powerful.