Fractional Knapsack | Algorithms - Computer Science Engineering (CSE) PDF Download

Introduction

The Fractional Knapsack Problem is a classic optimization problem where the objective is to fill a knapsack with items to maximize the total value (or profit) while staying within its weight capacity. It is about choosing items with specific weights and profits to maximize the total profit without exceeding a weight limit. It's solved using a greedy approach, where you prioritize items based on their profit-to-weight ratio. This variant is known as the Fractional Knapsack Problem.

Knapsack Algorithm

The weights (Wi) and profit values (Pi) of the items to be added in the knapsack are taken as an input for the fractional knapsack algorithm and the subset of the items added in the knapsack without exceeding the limit and with maximum profit is achieved as the output.

Algorithm

• Consider all the items with their weights and profits mentioned respectively.
• Calculate Pi/Wi of all the items and sort the items in descending order based on their Pi/Wi values.
• Without exceeding the limit, add the items into the knapsack.
• If the knapsack can still store some weight, but the weights of other items exceed the limit, the fractional part of the next time can be added.

• Hence, giving it the name fractional knapsack problem.

Problem Statement: The weight of N items and their corresponding values are given. We have to put these items in a knapsack of weight W such that the total value obtained is maximized.

Note: We can either take the item as a whole or break it into smaller units.

Example:

Input: N = 3, W = 50, values[] = {100,60,120}, weight[] = {20,10,30}.

Code Implementation

#include <bits/stdc++.h>

using namespace std;

struct Item {

   int value;

   int weight;

};

class Solution {

   public:

      bool static comp(Item a, Item b) {

         double r1 = (double) a.value / (double) a.weight;

         double r2 = (double) b.value / (double) b.weight;

         return r1 > r2;

      }

   // function to return fractionalweights

   double fractionalKnapsack(int W, Item arr[], int n) {

      sort(arr, arr + n, comp);

      int curWeight = 0;

      double finalvalue = 0.0;

      for (int i = 0; i < n; 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) arr[i].weight) * (double) remain;

            break;

         }

      }

      return finalvalue;

   }

};

int main() {

   int n = 3, weight = 50;

   Item arr[n] = { {100,20},{60,10},{120,30} };

   Solution obj;

   double ans = obj.fractionalKnapsack(weight, arr, n);

   cout << "The maximum value is " << setprecision(2) << fixed << ans;

   return 0;

}

Output: 240.00

Explanation: The first and second items  are taken as a whole  while only 20 units of the third item is taken. Total value = 100 + 60 + 80 = 240.00
Time Complexity: O(n log n + n). O(n log n) to sort the items and O(n) to iterate through all the items for calculating the answer.
Space Complexity: O(1), no additional data structure has been used.