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.

Fractional Knapsack | Algorithms - Computer Science Engineering (CSE)

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.

The document Fractional Knapsack | Algorithms - Computer Science Engineering (CSE) is a part of the Computer Science Engineering (CSE) Course Algorithms.
All you need of Computer Science Engineering (CSE) at this link: Computer Science Engineering (CSE)
81 videos|80 docs|33 tests

Top Courses for Computer Science Engineering (CSE)

FAQs on Fractional Knapsack - Algorithms - Computer Science Engineering (CSE)

1. What is Fractional Knapsack?
Ans. Fractional Knapsack is a type of problem in which items can be divided into fractions and placed into the knapsack, unlike 0/1 Knapsack where items cannot be divided.
2. How is the value per unit calculated in Fractional Knapsack?
Ans. The value per unit is calculated by dividing the total value of an item by its weight. This helps in determining which items provide the most value for their weight.
3. How is Fractional Knapsack different from 0/1 Knapsack?
Ans. In Fractional Knapsack, items can be divided into fractions and placed into the knapsack, whereas in 0/1 Knapsack, items cannot be divided and must be selected as a whole.
4. What is the time complexity of solving Fractional Knapsack using a greedy algorithm?
Ans. The time complexity of solving Fractional Knapsack using a greedy algorithm is O(n log n), where n is the number of items to be considered.
5. How does the greedy approach work in solving Fractional Knapsack?
Ans. The greedy approach in Fractional Knapsack involves sorting the items based on their value per unit and then selecting items greedily starting from the highest value per unit until the knapsack is full.
81 videos|80 docs|33 tests
Download as PDF
Explore Courses for Computer Science Engineering (CSE) exam

Top Courses for Computer Science Engineering (CSE)

Signup for Free!
Signup to see your scores go up within 7 days! Learn & Practice with 1000+ FREE Notes, Videos & Tests.
10M+ students study on EduRev
Related Searches

Important questions

,

MCQs

,

study material

,

Objective type Questions

,

Sample Paper

,

Summary

,

past year papers

,

Semester Notes

,

Fractional Knapsack | Algorithms - Computer Science Engineering (CSE)

,

pdf

,

shortcuts and tricks

,

video lectures

,

Fractional Knapsack | Algorithms - Computer Science Engineering (CSE)

,

practice quizzes

,

Fractional Knapsack | Algorithms - Computer Science Engineering (CSE)

,

Viva Questions

,

Previous Year Questions with Solutions

,

ppt

,

Extra Questions

,

Free

,

mock tests for examination

,

Exam

;