Fractional Knapsack | Solved using Greedy Algorithm

The Fractional Knapsack problem is one of the most famous problems in the Greedy Algorithm category. It is widely asked in coding interviews and also forms a key part of understanding optimization problems.

In this blog, we will go through the problem statement, understand why the greedy approach works here, and then look at the optimal Python implementation step by step.

Here’s the [Problem Link] to begin with.

Problem Statement – What Does the Problem Say?

You are given:

• A set of items, each with a value and a weight.
• A knapsack (bag) with a maximum capacity.

Your task is to:

• Fill the knapsack such that the total value is maximized.
• Unlike the 0/1 Knapsack problem, you are allowed to take fractions of items.

Example 1:

Input: 
val = [60, 100, 120] 
wt = [10, 20, 30] 
capacity = 50

Output: 240.0
Explanation:
- Pick item2 (value=100, weight=20) fully → remaining capacity = 30
- Pick item3 (value=120, weight=30) fully → remaining capacity = 0
Total value = 100 + 120 = 220

But better choice:
- Pick item1 (value=60, weight=10) fully → remaining capacity = 40
- Pick item2 (value=100, weight=20) fully → remaining capacity = 20
- Pick 2/3 fraction of item3 (value=120, weight=30) → add 80
Total value = 60 + 100 + 80 = 240

This shows why the greedy approach is important here.

Intuition and Approach (Optimal – Greedy)

The greedy idea comes from one key observation:

• To maximize value, we should always prefer items with the highest value-to-weight ratio first.

If we are allowed to take fractions of an item, then we can always pick as much as possible from the item that gives the best “value per unit weight.”

Steps to Solve:

1. For each item, calculate its value/weight ratio.
2. Sort all items in descending order of ratio.
3. Start filling the knapsack:
   • If the current item fits completely, take it.
   • If not, take only the fraction that fits in the remaining capacity.
4. Stop once the knapsack is full.

This ensures we always get the maximum possible value.

Code Implementation

Here’s the Python code for the Fractional Knapsack problem using the greedy method (with comments added for clarity):

class Solution:
    def fractionalknapsack(self, val, wt, capacity):
        # Build list of (value/weight ratio, value, weight) for each item
        # Ignore any items with zero weight to avoid division by zero
        items = [(v / w, v, w) for v, w in zip(val, wt) if w > 0]

        # Sort by ratio in descending order
        items.sort(key=lambda x: x[0], reverse=True)

        cur_weight = 0
        total_value = 0.0

        for ratio, v, w in items:
            if cur_weight + w <= capacity:
                # take the whole item
                cur_weight += w
                total_value += v
            else:
                # take only the fraction that fits
                remain = capacity - cur_weight
                if remain <= 0:
                    break
                total_value += ratio * remain
                break  # knapsack is full

        return total_value

Code Explanation

• We first prepare a list of items with their value-to-weight ratio along with their original value and weight.
• Then we sort the items by ratio in descending order, so that the best item (most profitable per unit weight) comes first.
• We start filling the knapsack:
  • If the item completely fits, we add its full value.
  • If it does not fit, we take only a fraction equal to the remaining capacity.
• The process stops as soon as the knapsack reaches full capacity.

This approach ensures that we are always choosing the most profitable option at every step, which is why greedy works here.

Time and Space Complexity

• Time Complexity:
  • Calculating ratios: O(n)
  • Sorting items: O(n log n)
  • Filling the knapsack: O(n)
  • Overall: O(n log n)
• Space Complexity:
  • We use extra space to store the list of items.
  • O(n) space.

So, the efficiency mainly comes from sorting.

Conclusion

The Fractional Knapsack problem is a classic example where the Greedy Algorithm gives the optimal solution. By always taking the item with the highest value-to-weight ratio, we can ensure that every unit of capacity is used in the most profitable way.

This method works in O(n log n) time due to sorting and is both clean and efficient for practical use.

For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.