Solving the Fractional Knapsack Problem

The Fractional Knapsack problem is a variant of the classic Knapsack problem. While the 0/1 Knapsack problem (discussed here) restricts you to either taking an item entirely or leaving it, the Fractional Knapsack problem allows you to take fractions of an item. This flexibility makes it suitable for situations where items can be divided into smaller parts.

Problem

Given a set of items, each with a weight w_i​ and a value v_i​, along with a knapsack of capacity W. Determine the maximum value (fractions amounts allowed) of items that can fit into the knapsack without exceeding its capacity.

Greedy Approach

We could solve the Fractional Knapsack problem with a greedy approach. We sort the items based on their value-to-weight ratios in non-increasing order. Then, starting with the item with the highest ratio, we greedily add fractions of items to the knapsack until it’s full.

Pseudocode

Sort items by decreasing value-to-weight ratio

totalValue = 0
remainingCapacity = knapsackCapacity

for each item in sortedItems:
    if remainingCapacity >= item.weight:
        // Take the whole item
        totalValue += item.value
        remainingCapacity -= item.weight
    else:
        // Take a fraction of the item
        fraction = remainingCapacity / item.weight
        totalValue += fraction * item.value
        remainingCapacity = 0
        break

return totalValue

Example

Consider the following items and their respective values and weights:

Let the knapsack capacity be 50. Let’s find the maximum value that can be obtained.

1. Calculating value-to-weight ratios for each item:
   - A: 60/10 = 6
   - B: 100/20 = 5
   - C: 120/30 = 4

2. Sort items by decreasing ratio:
   A > B > C

3. Fill the knapsack (capacity: 50) greedily:
   Add item A completely (remaining capacity = 50, value = 60, weight = 10)
   Add item B completely (remaining capacity = 40, value = 100, weight = 20)
   Add fraction of item C (remaining capacity = 20, value = 120, weight = 30, fraction used = 20/30)

3. Total Value:
   60*1 + 100*1 + 120*(20/30) = 240

Thus, maximum value that can be achieved is 240.

Note: If it had been the 0/1 Knapsack problem, the maximum value that could have been achieved is 220.

Code Implementation

//
//  main.cpp
//  Fractional Knapsack
//
//  Created by Himanshu on 11/03/24.
//

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;


struct Item {
    int value;
    int weight;
};

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

double fractionalKnapsack (int W, vector<Item>& items) {
    
    double totalValue = 0.0;
    int remainingCapacity = W;
    
    sort(items.begin(), items.end(), compare);

    for (auto item : items) {
        if (remainingCapacity >= item.weight) {
            // Take the whole item
            totalValue += item.value;
            remainingCapacity -= item.weight;
        } else {
            // Take a fraction of the item
            double fraction = (double)remainingCapacity / item.weight;
            totalValue += fraction * item.value;
            remainingCapacity = 0;
            break;
        }
    }

    return totalValue;
}

int main() {
    vector<Item> items = {{60, 10}, {100, 20}, {120, 30}};
    int knapsackCapacity = 50;
    
    double maxValue = fractionalKnapsack(knapsackCapacity, items);
    
    cout << "Maximum value obtained: " << maxValue << endl;
    
    return 0;
}

Output

Maximum value obtained: 240

Time complexity: O(n logn), n is the number of items
Auxiliary Space: O(n)

Explanation

Time complexity of the Fractional Knapsack algorithm is O(n logn), where n is the number of items. This is due to:

• First sorting the vector<> items of size n, which takes O(nlogn) time.
• And after sorting, proceeding linearly (O(n)) through the sorted list of items, taking constant time for each item.

Thus it takes O(n logn) time.

Space complexity of the algorithm is O(n), where n is the number of items. This space is primarily used to store the input items and the sorted list of items.