Fractional Knapsack Problem

Fractional Knapsack Problem

The Fractional Knapsack Problem is a variation of the 0/1 knapsack problem, where we can take fractions (or portions) of items, rather than having to decide whether to include or exclude each item entirely. This makes the problem easier to solve because you are allowed to break an item into smaller parts and take just a fraction of its total value or weight, depending on the knapsack's capacity.

Problem Statement:

• We are given n items, each with:
  • A value v[i]
  • A weight w[i]
• We are given a knapsack with a weight capacity W.
• Our goal is to determine the maximum value that can be obtained by selecting fractions of items such that the total weight does not exceed W.

Unlike the 0/1 Knapsack Problem, in the fractional version, we can take any fraction of an item, and the value of the fraction will be proportional to the amount of that item taken.

Greedy Approach:

The Fractional Knapsack Problem can be solved using a Greedy Algorithm, as it satisfies the greedy-choice property. This means that the locally optimal choice at each step (i.e., picking the most valuable item per unit weight) leads to a globally optimal solution.

Greedy Strategy:

1. Compute the value-to-weight ratio for each item:
   For each item i, calculate the ratio v[i] / w[i]. This ratio indicates the value we get per unit of weight.

2. Sort the items based on the value-to-weight ratio in descending order.

3. Take the items:

   • Start with the item with the highest value-to-weight ratio.
   • Take as much of this item as possible (up to the knapsack's remaining capacity).
   • If the remaining capacity is less than the item's weight, take the fraction of the item that fits.

4. Repeat for the next most valuable item until the knapsack is full or all items have been considered.

Mathematical Formulation:

Given items i with value v[i] and weight w[i], the value-to-weight ratio is:

ratio[i] = v[i] / w[i]

To maximize the value, we:

• Sort the items in descending order of the value-to-weight ratio.
• Take the fraction of the items that fits in the remaining capacity of the knapsack.

Steps to Solve:

1. Compute the value-to-weight ratio for each item.
2. Sort items based on the value-to-weight ratio.
3. Iterate over the sorted items, and for each item:
   • If the item can fully fit, take it completely.
   • If the item cannot fully fit, take the fraction that can fit.
4. Repeat the process until the knapsack is full or all items are processed.

Example:

Let's go through an example to better understand the solution.

Given:

• Knapsack capacity: W = 50
• Items with their values and weights:

Steps to Solve:

1. Compute value-to-weight ratios:

   • Item 1: $\frac{60}{10} = 6.0$
   • Item 2: $\frac{100}{20} = 5.0$
   • Item 3: $\frac{120}{30} = 4.0$

2. Sort the items based on the value-to-weight ratio (in descending order):

   • Item 1: 6.0
   • Item 2: 5.0
   • Item 3: 4.0

3. Start filling the knapsack:

   • Item 1: Weight = 10, Value = 60, Ratio = 6.0

     • Take the whole item (capacity left = 50 - 10 = 40).
     • Total value = 60.

   • Item 2: Weight = 20, Value = 100, Ratio = 5.0

     • Take the whole item (capacity left = 40 - 20 = 20).
     • Total value = 60 + 100 = 160.

   • Item 3: Weight = 30, Value = 120, Ratio = 4.0

     • The knapsack has only 20 capacity left. Take 20/30 of the item (fraction).
     • Fraction of value = $\frac{20}{30} \times 120 = 80$.
     • Total value = 160 + 80 = 240.

4. Knapsack is full with a total value of 240.

Greedy Algorithm Implementation in C++:

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

// Structure to represent an item
struct Item {
    int weight;
    int value;
    float ratio;  // Value-to-weight ratio
};

// Comparison function to sort items by value-to-weight ratio in descending order
bool compare(Item a, Item b) {
    return a.ratio > b.ratio;
}

// Function to solve Fractional Knapsack Problem
float fractionalKnapsack(int W, std::vector<Item>& items) {
    // Sort items by their value-to-weight ratio in descending order
    std::sort(items.begin(), items.end(), compare);

    float totalValue = 0.0f;
    for (auto& item : items) {
        if (W == 0) {
            break;
        }

        if (item.weight <= W) {
            // If the item can be fully included, take it completely
            totalValue += item.value;
            W -= item.weight;
        } else {
            // Otherwise, take the fraction of the item that fits
            totalValue += item.value * ((float)W / item.weight);
            W = 0;
        }
    }

    return totalValue;
}

int main() {
    int W = 50; // Knapsack capacity
    std::vector<Item> items = {
        {10, 60, 0.0f},  // Item 1
        {20, 100, 0.0f}, // Item 2
        {30, 120, 0.0f}  // Item 3
    };

    // Compute the value-to-weight ratio for each item
    for (auto& item : items) {
        item.ratio = (float)item.value / item.weight;
    }

    // Calculate the maximum value achievable
    float maxValue = fractionalKnapsack(W, items);
    
    std::cout << "Maximum value in knapsack = " << maxValue << std::endl;

    return 0;
}

Explanation of Code:

1. Item Structure: We define a structure Item to hold the weight, value, and value-to-weight ratio for each item.
2. Comparison Function: compare() sorts the items based on the value-to-weight ratio in descending order.
3. fractionalKnapsack(): This function implements the greedy algorithm to solve the fractional knapsack problem. It iterates through the sorted items and adds the item or its fraction to the knapsack.
4. Main Function: It initializes the items and computes the maximum value that can be packed into the knapsack.

Time Complexity:

• Time Complexity: O(n log n), where n is the number of items, due to sorting the items by the value-to-weight ratio.
• Space Complexity: O(n), where n is the number of items, for storing the items and their ratios.

Conclusion:

• The Fractional Knapsack Problem can be efficiently solved using a greedy approach, where we always pick the item with the highest value-to-weight ratio.
• Unlike the 0/1 knapsack problem, in the fractional version, we are allowed to take fractional parts of an item, which simplifies the problem and allows for an optimal solution.