Fractional Knapsack 🎯

Welcome to an exciting journey through the world of Data Structures and Algorithms! Today, we'll dive into a fascinating problem known as the Fractional Knapsack. This problem is a variant of the classic Knapsack Problem, and it's a must-know for any aspiring programmer. Let's get started!

Understanding the Problem 📝

Imagine you're a treasure hunter who's found a magical knapsack. This knapsack has a limited capacity, but it can hold items of any size, not just whole ones! The challenge is to fill the knapsack with items such that the total value of items is maximized without exceeding the knapsack's capacity.

Key Concepts 💡

Items: Each item has a value v and weight w. The value represents the benefit of having that item, while the weight represents its size.
Knapsack Capacity: The maximum weight the knapsack can hold.
Fractional Knapsack Problem (FKP): The problem of maximizing the total value of items in the knapsack, where items can be taken in parts (fractions).

Solving the Fractional Knapsack Problem 🎯

We'll be solving the FKP using the Greedy Algorithm. The idea is to always pick the item that provides the maximum value-to-weight ratio.

Example 1 📝

Let's consider the following items:

| Item No. | Weight w | Value v | Value-to-Weight Ratio v/w | |----------|-----------|----------|---------------------------| | 1 | 3 | 10 | 10/3 = 3.33 | | 2 | 4 | 20 | 20/4 = 5 | | 3 | 5 | 15 | 15/5 = 3 | | 4 | 6 | 25 | 25/6 = 4.17 | | 5 | 7 | 30 | 30/7 = 4.29 |

And a knapsack with a capacity of 15.

The greedy algorithm would first pick item 2 (4 units, giving 80% of its value), then item 3 (3 units, giving 60% of its value), and finally item 4 (3 units, giving 60% of its value). The total value obtained is 80% (from item 2) + 60% (from item 3) + 60% (from item 4) = 200% of the value of items that could fit into the knapsack.

Example 2 📝

Let's consider another scenario with a knapsack capacity of 10:

In this case, the greedy algorithm would first pick item 1 (3 units, giving 100% of its value), then item 2 (2 units, giving 100% of its value), and finally item 3 (2 units, giving 67% of its value). The total value obtained is 100% (from item 1) + 100% (from item 2) + 67% (from item 3) = 267% of the value of items that could fit into the knapsack.

Code Example 💻

Now, let's write a Python solution for the Fractional Knapsack Problem.

python

def fractional_knapsack(capacity, values, weights):
    values_weight_ratios = [value / weight for value, weight in zip(values, weights)]
    items = sorted(range(len(values)), key=lambda i: values_weight_ratios[i], reverse=True)

    knapsack = []
    for item in items:
        weight = weights[item]
        value = values[item]
        if capacity >= weight:
            knapsack.append((value, weight))
            capacity -= weight
        else:
            fraction = capacity / weight
            knapsack.append((fraction * value, weight))
            capacity = 0

    return sum([item[0] for item in knapsack])

# Test the function
values = [10, 20, 15, 25, 30]
weights = [3, 4, 5, 6, 7]
capacity = 15
print(fractional_knapsack(capacity, values, weights))  # Output: 200

Quiz 📝

That's it for today! We've covered the Fractional Knapsack Problem, learned how to solve it using the Greedy Algorithm, and even wrote a Python solution. Keep practicing and soon, you'll be a Data Structures and Algorithms whiz! 🎉🎓