Q:

# Fractional knapsack problem

We have given items i1i2, ..., in (item we want to put in our bag) with associated weights w1w2, ..., wn and profit values P1 , P2 ,..., Pn. 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 di = Pi / wi.
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);

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```