# Fractional Knapsack Problem

## Fractional Knapsack Problem

The Fractional Knapsack Problem is a variation of the 0-1 knapsack problem. The problem has a greedy solution. It is a very famous question. This question itself and its variations are asked in many interviews. In this article, we will provide a C++ code with an explanation. ## Fractional Knapsack Problem Description

Given n items each with its weight and value. Also given a knapsack of total capacity C. Fill items in the knapsack in such a way that the total value of items in the knapsack is maximum possible. Output the maximum possible value.

Note – We can put any fraction (<=1) of the item. The value will change accordingly.

Input

• First line contains two integers n and C – the number of items and the capacity of knapsack.
• Second line contains n integers the weight of n items.
• Third line contains n integers the value of the n items.

Output

• The maximum value possible.

## Fractional Knapsack Problem Solution

The problem can be solved using a greedy approach efficiently. Remember that we can take any fraction of a item and put into the knapsack. So it is always better for us to take item with maximum value per unit weight first.

Steps –

• Sort the items in decreasing order of value per unit weight.
• Loop over all items. Take the maximum weight of the item that can be taken into the knapsack.

Time Complexity – O(nlogn) as sorting is required.

### Code

#include <bits/stdc++.h>
using namespace std;
class item
{
public:
double wtval;
};
// sorting array of items by value per unit weight
bool compare(item Aitem B)
{
return A.val / A.wt > B.val / B.wt;
}
int main()
{
int n;
double cmxValue = 0;
cin >> n >> c;
item arr[n];

for (int i = 0i < ni++)
cin >> arr[i].wt;

for (int i = 0i < ni++)
cin >> arr[i].val;

sort(arrarr + ncompare);

for (int i = 0i < n && c > 0.0i++)
{
double x = min(arr[i].wtc);
/*
x is the weight or portion of item we can take
it can be either c(ie capacity left) or it’s own weight ie arr[i].wt
*/
c -= x; //Decreasing capacity

mxValue += (x * (arr[i].val / arr[i].wt));
}

cout << mxValue << endl;
return 0;
}

### Output

`3 51 2 36 10 1224`