Fractional Knapsack Problem

December 30, 2021

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

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 wt, val;
};
// sorting array of items by value per unit weight
bool compare(item A, item B)
{
    return A.val / A.wt > B.val / B.wt;
}
int main()
{
    int n;
    double c, mxValue = 0;
    cin >> n >> c;
    item arr[n];

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

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

    sort(arr, arr + n, compare);

    for (int i = 0; i < n && c > 0.0; i++)
    {
        double x = min(arr[i].wt, c);
        /*  
            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 5
1 2 3
6 10 12
24