How to Solve the Fractional Knapsack Problem in C++

Given a set of items, each with the given weight and profit, determine each number of items in such a combination that the total weight of items is less than the maximum limit of the bag, but the value must be kept as large as possible.

Algorithm To Implement the Fractional Knapsack Problem

The functioning of the Knapsack algorithm can be understood through the following points:

Take two arrays of weight and profit.
Set the maximum sack value to W.
Determine the density by taking the ratio of both parameters.
Sort items in decreasing order of density.
Add up values till it is <=W.

The Greedy Approach to Solve the Fractional Knapsack Problem

The greedy approach aims to make ideal choices at each step, leading to the ideal solution at the end. It solves problems step by step leading to conclusions instead of concluding the results in the end only. This is a source code for implementing a solution to the fractional knapsack problem in C++:

#include <bits/stdc++.h>

using namespace std;

struct Object {

int value, weight;

Object(int value, int weight)
: value(value), weight(weight)
{
}

};

bool cmp(struct Object x, struct Object y)

{

double A1 = (double)x.value / x.weight;

double A2 = (double)y.value / y.weight;

return A1 > A2;

}

double fractionalKnapsack(struct Object arr[],
int W, int size)
{

sort(arr, arr + size, cmp);

int curWeight = 0;

double finalvalue = 0.0;

for (int i = 0; i < size; i++) {

if (curWeight + arr[i].weight <= W) {
curWeight += arr[i].weight;
finalvalue += arr[i].value;
}

else {
int remain = W - curWeight;
finalvalue += arr[i].value
* ((double)remain
/ arr[i].weight);

break;
}
}

return finalvalue;

}

int v = 60;

Object arr[] = { { 100, 20 },
{ 380, 40 },
{ 140, 10 },
{ 180, 30 } };

int size = sizeof(arr) / sizeof(arr[0]);

cout << "Maximum profit = "

<< fractionalKnapsack(arr, v, size);

return 0;

}

In this code, an object structure is defined which has weight and profit values stored in it. The bool cmp() is used to make a comparison between two objects on the basis of the ratio of weight and value of two objects. The array is arranged in descending order and the value keeps on adding till it reaches maximum. If the current value is permissible and within the limit, it is added, otherwise its reduced ratio is added to the bag. The magnitude of weight and value is input in the main code and the maximum profit is printed on the output.

The maximum profit that was stored in the snack is 580.

Conclusion

The fractional knapsack problem in C++ refers to identifying a way to fill a bag with items of a given weight and profit in such a way that the bag contains the maximum value without exceeding the maximum limit. This can be achieved by the greedy approach that aims to make ideal choices at each step, leading to the ideal solution at the end.

How to Solve the Fractional Knapsack Problem in C++