Fractional Knapsack Problem

The Fractional Knapsack Problem is a popular topic in the world of algorithms and data structures, commonly taught to students and beginner programmers. It is a problem-solving technique used to maximize the total profit by selecting items within a given capacity. This problem allows us to break items into smaller pieces to maximize the total profit, unlike the 0/1 Knapsack problem, where we have to either include or exclude entire items.

In this article, we’ll dive into an easy-to-understand explanation of the Fractional Knapsack Problem, complete with a Python implementation, pseudocode, and an analysis of time and space complexity. Whether you’re a child learning Python or a beginner eager to understand algorithms, this guide is made simple and approachable just for you!

What is the Fractional Knapsack Problem?

Imagine you are packing a bag (knapsack) with a limited capacity, and you have several items with different weights and values. Your goal is to select items such that you can maximize the total profit from the items in your knapsack without exceeding its capacity. In the Fractional Knapsack Problem, you are allowed to take a fraction of an item rather than just the entire item, giving you flexibility in maximizing your profit.

Problem Statement

• You are given N items, each with a profit and a weight.
• You also have a knapsack with a fixed capacity W.
• You can take full or fractional parts of the items to maximize the profit.
• The goal is to maximize the profit within the knapsack’s weight limit.

Example Problem

Let’s consider the following example to understand the problem better:

• Items: [{value: 70, weight: 15}, {value: 80, weight: 20}, {value: 100, weight: 30}]
• Knapsack Capacity: 40

Now, let’s maximize the profit by selecting the best combination of items or their fractions.

Greedy Approach to Solve the Fractional Knapsack Problem

To solve the Fractional Knapsack Problem efficiently, we use a Greedy Algorithm. The greedy approach is simple: select the items based on the highest value-to-weight ratio and pack them as much as possible in the knapsack.

Why the Greedy Approach?

• Efficiency: The greedy algorithm is simple and provides an optimal solution for the Fractional Knapsack Problem. By selecting the most valuable items first, we can ensure the highest possible profit in the knapsack.
• Flexibility: Unlike the 0/1 Knapsack Problem, the Fractional Knapsack allows for dividing items into smaller parts, giving more flexibility in achieving the maximum profit.
• Optimal for Fractional Problems: The greedy method works best for problems where fractional choices are allowed.

Steps to Solve:

1. Calculate the Profit-to-Weight Ratio:
   For each item, calculate its value/weight ratio. The item with the highest ratio provides the most value for the least weight.
2. Sort Items by Ratio:
   Sort all the items in descending order based on their value/weight ratio.
3. Pick Items Based on Capacity:
   Start adding items with the highest ratio to the knapsack. If an item’s weight exceeds the remaining capacity, add a fraction of that item to the knapsack.
4. Maximize the Profit:
   Continue the process until the knapsack is full or there are no more items to add.

Detailed Example

Input:

Items = [{value: 70, weight: 15}, {value: 80, weight: 20}, {value: 100, weight: 30}]
Capacity = 40

Step-by-Step Process:

1. Calculate the value/weight ratios:
   • Item 1: 70/15 = 4.67
   • Item 2: 80/20 = 4.00
   • Item 3: 100/30 = 3.33
2. Sort the items based on the value/weight ratios:
   • Item 1 (4.67), Item 2 (4.00), Item 3 (3.33)
3. Pick items for the knapsack:
   • Start with Item 1: It weighs 15, and the remaining capacity is 40 – 15 = 25.
   • Pick Item 2: It weighs 20, and the remaining capacity is 25 – 20 = 5.
   • Pick 5/30 of Item 3 (fraction): Profit = 5/30 * 100 = 16.67.
4. Final Profit:
   • Total profit = 70 (Item 1) + 80 (Item 2) + 16.67 (fraction of Item 3) = 166.67.

Output:

Maximum profit = 166.67

Pseudocode for Fractional Knapsack Problem

def fractional_knapsack(values, weights, capacity):
    # Step 1: Calculate value-to-weight ratio
    items = []
    for i in range(len(values)):
        items.append((values[i] / weights[i], values[i], weights[i]))

    # Step 2: Sort items by the ratio
    items.sort(reverse=True, key=lambda x: x[0])

    # Step 3: Initialize variables for profit and remaining capacity
    total_profit = 0
    remaining_capacity = capacity

    # Step 4: Iterate through sorted items
    for ratio, value, weight in items:
        if weight <= remaining_capacity:
            # Take the whole item
            total_profit += value
            remaining_capacity -= weight
        else:
            # Take fractional part of the item
            total_profit += ratio * remaining_capacity
            break

    return total_profit

Python Implementation OF Fractional Knapsack

def fractional_knapsack(values, weights, capacity):
    items = []
    for i in range(len(values)):
        items.append((values[i] / weights[i], values[i], weights[i]))

    # Sort items by their value/weight ratio
    items.sort(reverse=True, key=lambda x: x[0])

    total_profit = 0
    remaining_capacity = capacity

    for ratio, value, weight in items:
        if weight <= remaining_capacity:
            total_profit += value
            remaining_capacity -= weight
        else:
            total_profit += ratio * remaining_capacity
            break

    return total_profit


# Example Usage
values = [70, 80, 100]
weights = [15, 20, 30]
capacity = 40
print("Maximum Profit:", fractional_knapsack(values, weights, capacity))

Time and Space Complexity

Time Complexity:

• Sorting the items based on their value-to-weight ratio takes O(N log N), where (N) is the number of items.
• Iterating through the items takes (O(N)).
• Overall Time Complexity: O(N log N)

Space Complexity:

• We need space to store the value-to-weight ratios, which takes (O(N)).
• Overall Space Complexity: (O(N))

Conclusion

The Fractional Knapsack Problem is an excellent way to learn about optimization techniques using a greedy approach. By breaking the problem into simple steps, calculating profit-to-weight ratios, and selecting items wisely, you can efficiently solve this problem. With the Python implementation and pseudocode provided, you can start experimenting with the algorithm and enhance your problem-solving skills!