Fractional Knapsack Using C++

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.

What Is Fractional Knapsack?

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.

Fractional Knapsack Algorithm

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.

What Is A Greedy Algorithm?

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.

Strategy To Work With Greedy Algorithms

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.

Pseudocode

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.
• 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 capacity becomes 0, break out of the loop.

The overall structure of the pseudocode becomes:

C++ Program To Demonstrate Fractional Knapsack

#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;
}

Output

Conclusion

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.

Further Reading

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

https://brilliant.org/wiki/greedy-algorithm

https://en.wikipedia.org/wiki/Knapsack_problem