What is Fractional Knapsack Problem?

Last updated on December 19th, 2024 at 05:22 pm

This article explores the Fractional Knapsack Problem and examples and explores how to solve it using programming languages like C++, Java, and Python.

1. What is Fractional Knapsack Problem?

The Fractional Knapsack Problem is a classic optimization problem that can be solved using a greedy algorithm. In this problem, items are given along with their weight and profit. The target is to maximize the profit considering the weight constraint.

Unlike the 0/1 Knapsack problem, you can take fractions of items, meaning you can break the items into smaller pieces.

Imagine you’re a thief with a bag (knapsack) that can hold a limited weight. You have several items to choose from, each with a specific weight and value. The goal is to maximize the total value of the items in your bag without exceeding its weight limit.

1.1 Solution by Greedy Algorithm

1. In fractional knapsack, first of all, profit value/weight ratios are calculated and then sorted in descending order.
2. An item with the highest value/weight ratio is chosen and added to the collection.
3. The maximum weight is checked after adding each item.
4. If the entire item cannot be included, then a fraction of it is added to the collection.

2. Why is the Fractional Knapsack Important?

The Fractional Knapsack Problem is important because it models real-world scenarios where resources are divisible. For example:

• Logistics: Distributing goods across limited storage space.
• Finance: Allocating investments to maximize returns.
• Supply Chain: Optimizing resource usage in production.

3. Fractional Knapsack Problem Example

Let’s look at a simple example:

You have a knapsack with a weight limit of 50 kg. You’re given the following items:

Steps to Solve:

1. Calculate the value-to-weight ratio for each item.
2. Sort the items by their ratio in descending order.
3. Add items to the knapsack starting with the highest ratio. If the knapsack can’t hold the full weight of an item, take a fraction of it.

Solution:

• Take all of Item A (10 kg, $60).
• Take all of Item B (20 kg, $100).
• Take 2/3 of Item C (20 kg, $80).

Total Value: $240

4. Fractional Knapsack Pseudocode

Simple pseudocode to solve the Fractional Knapsack Problem:

Input: capacity, weights, values
Output: maximum value

1. Sort items by value/weight ratio in descending order
2. Initialize total value and remaining capacity
3. For each item:
   a. If remaining capacity >= weight, add item to knapsack and update remaining capacity
   b. Else, add fraction of item to knapsack and update remaining capacity
4. Return maximum value

5. Solving the Fractional Knapsack Problem in Programming

5.1 Fractional Knapsack C++ Implementation

#include <iostream>
#include <vector>
#include <algorithm>

struct Item {
    int value, weight;
};

bool compare(Item a, Item b) {
    double r1 = (double)a.value / a.weight;
    double r2 = (double)b.value / b.weight;
    return r1 > r2;
}

double fractionalKnapsack(int W, std::vector<Item> &arr, int n) {
    sort(arr.begin(), arr.end(), compare);
    double totalValue = 0.0;
    for (int i = 0; i < n; i++) {
        if (arr[i].weight <= W) {
            W -= arr[i].weight;
            totalValue += arr[i].value;
        } else {
            totalValue += arr[i].value * ((double) W / arr[i].weight);
            break;
        }
    }
    return totalValue;
}

int main() {
    int W = 50;
    std::vector<Item> arr = {{60, 10}, {100, 20}, {120, 30}, {160, 40}};
    int n = arr.size();
    std::cout << "Maximum value we can obtain = " << fractionalKnapsack(W, arr, n);
    return 0;
}

5.2 Fractional Knapsack Java Implementation

import java.util.Arrays;
import java.util.Comparator;

class Item {
    int value, weight;
    Item(int x, int y) {
        this.value = x;
        this.weight = y;
    }
}

class Main {
    static double fractionalKnapsack(int W, Item arr[], int n) {
        Arrays.sort(arr, new Comparator<Item>() {
            @Override
            public int compare(Item item1, Item item2) {
                double r1 = (double)item1.value / item1.weight;
                double r2 = (double)item2.value / item2.weight;
                return r2 > r1 ? 1 : -1;
            }
        });

        double totalValue = 0.0;
        for (int i = 0; i < n; i++) {
            if (arr[i].weight <= W) {
                W -= arr[i].weight;
                totalValue += arr[i].value;
            } else {
                totalValue += arr[i].value * ((double) W / arr[i].weight);
                break;
            }
        }
        return totalValue;
    }

    public static void main(String[] args) {
        int W = 50;
        Item arr[] = {new Item(60, 10), new Item(100, 20), new Item(120, 30), new Item(160, 40)};
        int n = arr.length;
        System.out.println("Maximum value we can obtain = " + fractionalKnapsack(W, arr, n));
    }
}

5.3 Fractional Knapsack Python Implementation

class Item:
    def __init__(self, value, weight):
        self.value = value
        self.weight = weight

def fractionalKnapsack(W, arr):
    arr.sort(key=lambda x: x.value/x.weight, reverse=True)
    totalValue = 0.0
    for item in arr:
        if item.weight <= W:
            W -= item.weight
            totalValue += item.value
        else:
            totalValue += item.value * (W / item.weight)
            break
    return totalValue

if __name__ == "__main__":
    W = 50
    arr = [Item(60, 10), Item(100, 20), Item(120, 30), Item(160, 40)]
    n = len(arr)
    print("Maximum value we can obtain =", fractionalKnapsack(W, arr))

6. Advantages of Fractional Knapsack

1. Efficiency: The greedy approach ensures that we get the optimal solution in a relatively simple and efficient manner.
2. Flexibility: Allows for taking fractions of items, which can be practical in real-world scenarios.

7. Disadvantages of Fractional Knapsack

1. Limited Scope: Only applicable to problems where items can be divided. It doesn’t work for 0/1 Knapsack problems.
2. Sorting Overhead: The need to sort items by their value-to-weight ratio adds to the complexity, making the algorithm O(n log n).

8. Time Complexity of Fractional Knapsack

If the ratio of v_i/w_i is already sorted in decreasing order, then the time taken by the while loop will be O(n). So, the total time required will be O(n log n).

FAQs