While we believe that this content benefits our community, we have not yet thoroughly reviewed it. If you have any suggestions for improvements, please let us know by clicking the “report an issue“ button at the bottom of the tutorial.

In this article, we will learn to solve the fractional knapsack problem using C++. We will start by looking at the problem statement and then move to the solution. This problem is one of many popular classical problems. It is fairly different than its sibling 0-1 knapsack and 0-N knapsack. This is a greedy algorithm and the other two are dynamic programming algorithms.

*You are given the list of weight and prices of certain items and a bag/knapsack of certain capacity say W. Your task is to fill this bag in such a manner that the total price of all the items that you take in this bag is maximum for all the configurations. And you can either collect any object as a whole or a fraction of it.*

Okay, let’s look at the algorithm to solve this problem. Since we will be implementing a greedy solution to this problem, below is a brief description of greedy algorithms.

In these algorithms, we aim to achieve a local maximum/minimum at each step in order to achieve a global maximum/minimum in the end. That is, we maximize/minimize the answer to each of the subproblems and it leads us to the maximum/minimum answer of the overall problem.

`Note:`

The greedy choice that you are going to make must be a safe move.

`Safe Move:`

A move is called a safe move if there exists an optimal answer reliable with this initial move.

Below are the steps that you should follow to develop a perfect greedy algorithm.

- Make a greedy choice
*Prove*that it is a*safe move*so that you don’t write the code and find out in the end that it was not a feasible choice. This particular step is the most important step of greedy algorithms.- Reduce to a smaller problem
- Solve all the smaller problems.

Now we will go through the knapsack algorithm, step by step.

- Sort the items in decreasing order of value/weight ratio. This step alone decreases the time complexity of selection of the best item from
`O(N)`

to`O(log2N)`

. - Now we start selecting the objects by running a
*for loop from i = 0 to i = N* `Lemma:`

There exists an optimal solution that uses as much as possible of an item with the maximum value per unit of weight.- Proof: Try filling the knapsack by a different selection criteria, you will always get smaller total value than the maximum possible value.

The example attached below proves that our lemma is correct.

- Now if the size of the item with maximum value/weight ratio fits the knapsack, take the whole of it. Otherwise, take the maximum possible fraction of it.
- Reduce the capacity of the bag by the weight of the item taken.
- If the whole item is taken then:
`capacity = capacity - weight[this_item]`

. - Otherwise, the capacity becomes 0 because the knapsack becomes full.

- If the whole item is taken then:
- Add the value of the fraction of this item taken to the total value.
- If the whole item is taken:
`total_value += value[this_item]`

- Otherwise, the
`value += fraction_of_weight_taken * value[this_item]`

.

- If the whole item is taken:
- If capacity becomes 0, break out of the loop.

The overall structure of the pseudocode becomes:

```
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
// this custom comparator function will allow
// us to compare our vector based on the
// ratio of values to weights
bool compare(pair <float, int> p1, pair <float, int> p2)
{
return p1.first > p2.first;
}
int fractional_knapsack(vector <int> weights, vector <int> values, int capacity)
{
int len = weights.size();
int total_value = 0;
// vector to store the items based on their value/weight ratios
vector <pair <float, int>> ratio(len, make_pair(0.0, 0));
for(int i = 0; i < len; i++)
ratio[i] = make_pair(values[i]/weights[i], i);
// now sort the ratios in non-increasing order
// for this purpose, we will use our custom
// comparator function
sort(ratio.begin(), ratio.end(), compare);
// start selecting the items
for(int i = 0; i < len; i++)
{
if(capacity == 0)
break;
int index = ratio[i].second;
if(weights[index] <= capacity)
{
// we item can fit into the knapsack
// hence take the whole of it
capacity -= weights[index];
// add the value of this item to the
// final answer
total_value += values[index];
}
else
{
// this item doesn't fit into the bag
// and thus we take a fraction of it
int value_to_consider = values[index] * (float(capacity)/float(weights[index]));
total_value += value_to_consider;
capacity = 0;
}
}
return total_value;
}
int main()
{
cout << "Enter the weights of the items, press -1 to stop" << endl;
vector <int> weights;
while(true)
{
int weight;
cin >> weight;
if(weight == -1)
break;
weights.push_back(weight);
}
cout << "Enter the values of each item, press -1 to stop" << endl;
vector <int> values;
while(true)
{
int value;
cin >> value;
if(value == -1)
break;
values.push_back(value);
}
cout << "Enter the capacity of the knapsack" << endl;
int capacity;
cin >> capacity;
cout << "The maximum value possible based on current list is: " << fractional_knapsack(weights, values, capacity) << endl;
}
```

The fractional knapsack is a greedy algorithm, and in this article, we looked at its implementation. We learned in brief about the greedy algorithms, then we discussed the pseudocode of the fractional knapsack algorithm. We proved that our greedy choice is a safe move, and in the end, we wrote a C++ program to demonstrate this solution. The overall time complexity of this concept is: `O(Nlog2N)`

. This is it for today, thanks for reading.

If you want to learn more about knapsack and other greedy algorithms, you can refer to the following websites.

Join our DigitalOcean community of over a million developers for free! Get help and share knowledge in our Questions & Answers section, find tutorials and tools that will help you grow as a developer and scale your project or business, and subscribe to topics of interest.

Sign up