Fractional Knapsack Problem
What you'll learn: How to maximize the value you can carry in a knapsack when you're allowed to take fractions of items, using a greedy approach based on value-to-weight ratio.
The Core Problem
Imagine you're a treasure hunter with a backpack that holds a limited weight. You've found items with different values and weights. Unlike the classic 0/1 knapsack problem, here you can take parts of items—like scooping half a pile of gold dust instead of needing the whole pile.
The question: which items (or fractions of items) should you take to maximize total value?
The Greedy Strategy
The key insight is to be greedy about efficiency: prioritize items that give you the most "bang for your buck"—the highest value per unit of weight.
Algorithm Steps:
- Calculate value-to-weight ratio for each item
- Sort items by this ratio in descending order (highest first)
- Fill the knapsack greedily:
- Take as much as possible of the highest-ratio item
- If capacity remains, move to the next item
- Continue until the knapsack is full
Why This Works
The greedy choice property holds here: at every step, taking the most efficient item available (or as much as fits) leads to the globally optimal solution. Since we can take fractions, there's never a reason to skip a high-efficiency item for a lower one.
Example
Items: [(value=60, weight=10), (value=100, weight=20), (value=120, weight=30)]
Capacity: 50
Ratios: [6, 5, 4]
Take all of item 1 (10kg), all of item 2 (20kg), then 20/30 of item 3.
Total value: 60 + 100 + (120 × 20/30) = 240
Key Takeaway: The Fractional Knapsack Problem is solved optimally using a greedy approach by sorting items by value-to-weight ratio and filling the knapsack with the most efficient items first, taking fractions when necessary.