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:

Item | Value | Weight |
---|---|---|

A | 60 | 10 |

B | 100 | 20 |

C | 120 | 30 |

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.