Home » Interview coding problems/challenges

Fractional knapsack problem

In this article, we are discussing practical implementation of fractional knapsack problem. It can be solve using the greedy approach. Submitted by Vivek Kothari, on December 02, 2018

Prerequisites: Algorithm for fractional knapsack problem

Here, we are discussing the practical implementation of the fractional knapsack problem. It can be solved using the greedy approach and in fractional knapsack problem, we can break items i.e we can take a fraction of an item. For examples, you can read this article first.

Problem statement: We have given items i₁, i₂, ..., i_n (item we want to put in our bag) with associated weights w₁, w₂, ..., w_n and profit values P₁ , P₂ ,..., P_n. Now problem is how we can maximize the total benefit given capacity of bag is C?

Algorithm

1. Compute the profit per weight density for each item using the formula d_i = P_i / w_i.
2. Sort each item by its profit per weight density.
3. Maximize the profit i.e Take as much as possible of the profit per weight density item not already in the bag.

C++ implementation of fractional knapsack problem

#include <bits/stdc++.h> 

using namespace std; 

// Structure for an item
struct myItem 
{
	int itemNo; 
	int profit;
	int weight;
	float ppw; // profit per weight
}; 

// Comparison function to sort Item according to profit per weight ratio
bool cmp(struct myItem a, struct myItem b) 
{ 
	return a.ppw > b.ppw; 
} 

float fractionalKnapsack(int Capacity, struct myItem arr[], int n) 
{ 
	//calculating profit per weight ratio
	for(int i=0;i<n;i++)
	{
		arr[i].ppw = ((float)arr[i].profit / arr[i].weight);
	}

	// sorting Item on basis of profit per weight ratio 
	sort(arr, arr + n, cmp); 

	cout<<"details of all items : \n";
	cout<<"itemNo\t"<<"Profit\t"<<"Weight\t"<<"PPW\t"<<endl;
	for (int i = 0; i < n; i++) 
	{ 
		cout <<arr[i].itemNo<<"\t"<<arr[i].profit<<"\t"<<arr[i].weight<<"\t"<<((float)arr[i].ppw)<<endl; 
	}

	cout<<endl;

	float Max = 0.0; // Maximum profit
	int i=0; 

	//take items until capacity becomes zero
	while(Capacity > 0 && i<=n-1)
	{
		// if we can take all weights of item
		if(Capacity >= arr[i].weight)
		{
			Max = Max + (float)arr[i].profit;
			Capacity = Capacity - arr[i].weight;
		}
		// we can take only fraction of item
		else
		{
			Max += (Capacity * arr[i].ppw);
			Capacity = 0;
		}
		i++;
	}  

	return Max; 
} 

// driver function
int main() 
{ 
	int C = 25;   //    Capacity of knapsack 
	myItem arr[] = { {1, 30, 10, 0}, {2, 20, 5, 0} , {3, 40, 15, 0}, {4, 36, 8, 0}}; 

	int n = sizeof(arr) / sizeof(arr[0]);

	cout<<"details of all items before sorting and without calculating PPW: \n";
	cout<<"itemNo\t"<<"Profit\t"<<"Weight\t"<<"PPW\t"<<endl;
	for (int i = 0; i < n; i++) 
	{ 
		cout <<arr[i].itemNo<<"\t"<<arr[i].profit<<"\t"<<arr[i].weight<<"\t"<<((float)arr[i].ppw)<<endl; 
	} 

	cout<<endl;
	cout << "Maximum profit we can obtain = "<< fractionalKnapsack(C, arr, n);

	return 0; 
} 

Output

details of all items before sorting and without calculating PPW:
itemNo  Profit  Weight  PPW
1       30      10      0
2       20      5       0
3       40      15      0
4       36      8       0

details of all items :
itemNo  Profit  Weight  PPW
4       36      8       4.5
2       20      5       4
1       30      10      3
3       40      15      2.66667

Maximum profit we can obtain = 91.3333