Chapter 47

Home

Fractional Knapsack

You have a knapsack that holds W kg. Items have weight and value — but you can take any fraction of an item (like 0.3 kg of gold dust). The greedy solution is obvious: take the most valuable per unit weight first. This is the one knapsack variant where greedy is optimal.

The Setup

Given items with weight wᵢ and value vᵢ, fill a knapsack of capacity W. You can take any fraction of any item. Maximise total value.

Items: (value, weight) Gold: $100/kg — best ratio, take all Silver: $60/kg — take all Lead: $10/kg — take remaining capacity ← sorted by value/weight ↓

C++ — fractional knapsack

struct Item { double value, weight; };

double fractional_knapsack(vector<Item>& items, double capacity) {
    // Sort by value/weight ratio (descending)
    sort(items.begin(), items.end(),
         [](auto& a, auto& b) {
             return a.value / a.weight > b.value / b.weight;
         });

    double total_value = 0;
    for (auto& item : items) {
        if (capacity >= item.weight) {
            // Take the whole item
            total_value += item.value;
            capacity -= item.weight;
        } else {
            // Take a fraction
            total_value += item.value * (capacity / item.weight);
            break;
        }
    }
    return total_value;
}

Rust — fractional knapsack

struct Item { value: f64, weight: f64 }

fn fractional_knapsack(mut items: Vec<Item>, mut capacity: f64) -> f64 {
    items.sort_by(|a, b| {
        let ra = a.value / a.weight;
        let rb = b.value / b.weight;
        rb.partial_cmp(&ra).unwrap()  // descending
    });

    let mut total = 0.0;
    for item in &items {
        if capacity >= item.weight {
            total += item.value;
            capacity -= item.weight;
        } else {
            total += item.value * (capacity / item.weight);
            break;
        }
    }
    total
}

💡 Why greedy works here but not for 0/1 knapsack

With fractional items, you can always take "as much as you can" of the best ratio item, then move to the next. There's no "all or nothing" decision that forces you to skip a high-ratio item because of indivisible weight. The 0/1 knapsack (take whole or leave) breaks the greedy choice property — you might need to skip a dense item to make room for two lighter ones.

Worked Example

Items:          A ($60, 10kg)  B ($100, 20kg)  C ($120, 30kg)
Ratios (¢/kg):   600             500              400
Capacity: 50 kg

Greedy picks:
  1. A: whole item → $60, used 10kg, remaining 40kg
  2. B: whole item → $100, used 20kg, remaining 20kg
  3. C: fraction → $120 × (20/30) = $80, remaining 0kg

Total: $60 + $100 + $80 = $240  ✓ optimal

Key Takeaways

Practice