Course contentsShow
← Computer Science
Lesson 889 of 2,87221. Greedy AlgorithmsFree lesson

Fractional Knapsack Problem

Maximize value in a knapsack by taking fractional amounts of items, sorting by value-to-weight ratio.

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:

  1. Calculate value-to-weight ratio for each item
  2. Sort items by this ratio in descending order (highest first)
  3. 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.