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

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.


  • 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.


  • 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.


#include <bits/stdc++.h>
using namespace std;
class item
    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;


3 5
1 2 3
6 10 12