Fractional Knapsack Problem

In the previous lesson, we solved the Activity Selection Problem using a greedy strategy.

Now we move to another classic greedy problem — the Fractional Knapsack Problem.

This problem helps us understand how greedy decisions based on ratios can lead to optimal results when partial choices are allowed.

The Problem Statement

You are given a set of items.

Each item has:

• A weight
• A value

You also have a knapsack with a fixed maximum capacity.

Your goal is to maximize the total value inside the knapsack.

Unlike the 0/1 Knapsack problem, you are allowed to take fractions of items.

Real-World Interpretation

Imagine loading a delivery truck with bags of grain.

Each bag has a certain weight and market value.

If the truck is almost full, you can load only a part of the last bag.

The challenge is to choose the most valuable grain per unit weight.

The Greedy Insight

The key greedy idea is simple:

Always choose the item with the highest value-to-weight ratio.

This ensures that for every unit of weight added, we gain the maximum possible value.

Because fractional choices are allowed, this greedy choice is always optimal.

Step-by-Step Strategy

First, compute the value-to-weight ratio for each item.

Then, sort all items in descending order of this ratio.

Add items to the knapsack starting from the highest ratio.

If the remaining capacity cannot fit the entire item, take only the required fraction.

Worked Example

Suppose we have the following items:

Item A: value = 60, weight = 10
Item B: value = 100, weight = 20
Item C: value = 120, weight = 30

Knapsack capacity = 50

Value-to-weight ratios:

A = 6, B = 5, C = 4

We take:

• Entire item A (weight 10)
• Entire item B (weight 20)
• 2/3 of item C (weight 20)

This gives the maximum total value.

Pseudocode Explanation

sort items by value/weight ratio (descending)

remaining_capacity = knapsack_capacity
total_value = 0

for each item:
    if item.weight <= remaining_capacity:
        take whole item
        total_value += item.value
        remaining_capacity -= item.weight
    else:
        fraction = remaining_capacity / item.weight
        total_value += item.value * fraction
        break

This algorithm stops as soon as the knapsack becomes full.

Time Complexity

Sorting the items takes O(n log n).

Filling the knapsack takes O(n).

Overall complexity:

O(n log n)

Why This Greedy Strategy Works

The key reason is that fractional choices are allowed.

We never waste capacity on a low-value item when a higher-value fraction is available.

This property does NOT hold for the 0/1 Knapsack problem, which requires dynamic programming.

Mini Practice

Think carefully:

• Why does allowing fractions change the solution strategy?
• What would happen if items were chosen by highest value only?

Exercises

Quick Quiz

The Fractional Knapsack Problem shows how powerful greedy strategies can be when the problem structure allows flexibility.

In the next lesson, we will study another greedy application — Huffman Coding.