Fractional Knapsack Problem using nested pairing in STL

Given weights and values of n items, we need to put these items in a knapsack of capacity W to get the maximum total value in the knapsack.

In Fractional Knapsack, we can break items for maximizing the total value of the knapsack. This problem in which we can break an item is also called the fractional knapsack problem.

Example 1:Input:
Number of items, N = 5;
Knapsack Capacity, W = 20;
Values, 21 24 12 40 30
Weights, 7 4 6 5 6

Output:
Maximum possible value = 109
By taking items of 40, 24, 30 and 5/7 fraction of 21 kg.
Hence, the total price will be 40 + 24 + 30 + (5/7)(21) = 109
Example 2:
Input:
Number of items, N = 3;
Knapsack Capacity, W = 50;
Values, 60 100 120
Weights, 10 20 30 

Output:
Maximum possible value = 240
By taking items of weight 10 kg and 20 kg and 2/3 fraction of 30 kg. 
Hence total price will be 60 + 100 + (2/3)(120) = 240

An efficient solution is to use triplet pairing, i.e. nested pairing of weights, values, and values per unit weight. The basic idea of this approach is to form triplets using pairs in STL. So that operations on our dataset can be done more easily and optimally.

In this code, we have used vector of nested pairs and formed triplets of value/weight, values, and weights. Then, we have sorted the vector elements on the basis of values per unit weight and considered maximum values per unit weight to include in our capacity, So that we can get the maximum value possible.

Below is the implementation of the above idea:

Output:
Maximum value we can obtain = 109

As the main time taking step is sorting, the whole problem can be solved in O(n log n) only.
This article is contributed by Jayesh Thani.