# 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 i1, i2, ..., in (item we want to put in our bag) with associated weights w1, w2, ..., 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
```

TOP Interview Coding Problems/Challenges

Languages: » C » C++ » C++ STL » Java » Data Structure » C#.Net » Android » Kotlin » SQL
Web Technologies: » PHP » Python » JavaScript » CSS » Ajax » Node.js » Web programming/HTML
Solved programs: » C » C++ » DS » Java » C#
Aptitude que. & ans.: » C » C++ » Java » DBMS
Interview que. & ans.: » C » Embedded C » Java » SEO » HR
CS Subjects: » CS Basics » O.S. » Networks » DBMS » Embedded Systems » Cloud Computing
» Machine learning » CS Organizations » Linux » DOS
More: » Articles » Puzzles » News/Updates