Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
1.1.
Sample Examples
2.
Brute Force Approach 
3.
Optimized Approach(Greedy Method)
3.1.
Algorithm
3.2.
C++ Code
3.2.1.
Complexity Analysis
4.
Frequently asked questions
5.
Key takeaways
Last Updated: Mar 27, 2024

Fractional Knapsack Problem

Author Vaibhav Agarwal
2 upvotes
gp-icon
Competitive programming
Free guided path
16 chapters
99+ problems
gp-badge
Earn badges and level up

Introduction

This blog will discuss the brute and optimal approaches to solve the problem of a fractional knapsack. The question states that we have some items, let say x, and we have their weights and values. We need to put them into the knapsack of capacity W, and in we can break the item into parts to get the maximum possible value in a knapsack. Before deep-diving into the solution approaches, we will first discuss sample examples to understand the problem better.

Sample Examples

 Input is given in {value, weight} pairs.

Input : arr[] = {{10,10},{2,5},{6,8},{4,50},{100,1}}
            Knapsack Capacity, W = 25
Output: 118.08

Explanation: 
We will take items with value 1kg, 10kg,8kg, 5kg and 1/50 fraction of 50kg, so total value will be equal to 100 + 10 + 6 + 2 + (1/50)*4 = 118.08 which is maximum possible value in a knapsack.

 

Input : arr[] = {{1,10},{2,3},{2,2},{6,1},{4,5}}
          Knapsack Capacity, W = 6
Output : 10.4 

Explanation: 
We will take items with a value 1kg, 2kg, and 3/5 fraction of 5kg, so the total value will be equal to 6 + 2 +3/5 *(4) = 10.4, which is the maximum possible value in a knapsack.

Brute Force Approach 

In the brute force approach, we will generate all possible subsets with all possible fractions, calculate the sum of each subset, and take the maximum among all possible values. 

The time complexity of this solution is exponential, as finding all possible subsets is an exponential operation. 

Also see, Euclid GCD Algorithm

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Optimized Approach(Greedy Method)

This problem can be solved using the greedy technique. We will find all the value/weight ratios for each element and then sort the items in descending order according to the ratio. We will then start choosing items greedily, beginning with the maximum ratio.

Algorithm

  1. Sort the array in decreasing order using the value/weight ratio. 
  2. Start taking the element having the maximum value/weight ratio.
  3. If the weight of the current item is less than the current knapsack capacity, add the whole item, or else add the portion of the item to the knapsack. 
  4. Stop adding the elements when the capacity of the knapsack becomes 0
  5. Now we will have the maximum possible value in a knapsack. 

C++ Code

#include <bits/stdc++.h>
using namespace std;
//maximum possible value in a knapsack
// class Item which stores weight and
// corresponding value of Item
class Item {
    public:
        int value, weight;

        // Constructor
        Item(int value, int weight){
            this->value=value;
            this->weight=weight;
        }
};

// Comparison function to sort Item according to value/weight ratio
bool compare(Item x, Item y){
    // finding the ratio for xth item
    double ratio1 = (double)x.value / (double)x.weight;
    // finding the ratio for yth item
    double ratio2 = (double)y.value / (double)y.weight;
    return ratio1 > ratio2;
}

// Main greedy function to solve problem
Void fractionalKnapsack(int W, class Item arr[], int n){
    // sorting Item in descending order according to value/weight ratio
    sort(arr, arr + n, compare);
    // Current weight in knapsack
    int currentWeight = 0;
    // maximum possible value in knapsack
    double maxValue = 0.0;

    // Looping through all Items
    for (int i = 0; i < n; i++) {
        // If adding Item won't overflow, add it completely
        if (currentWeight + arr[i].weight <= W) {
            currentWeight += arr[i].weight;
            maxValue += arr[i].value;
        }

        // If we can't add current Item, add fraction of it into knapsack and break
        else {
            int fraction = W - currentWeight;
            maxValue += arr[i].value * ((double)fraction/(double)arr[i].weight);
            break;
        }
    }

    // printing the maximum possible value
    cout << maxValue;
}

// Driver code
int main()
{
    // Weight of knapsack
    int W = 25;
    //
    Item arr[] = {{10,10},{2,5},{6,8},{4,50},{100,1}};
    int n = sizeof(arr) / sizeof(arr[0]);
    // calling the knapsack function
    fractionalKnapsack(W, arr, n);
    return 0;
}

Complexity Analysis

Time Complexity: O(NlogN)

Explanation: We are using sorting here, and in the average case, sorting has TC of O(N log N). So Time Complexity is O(NlogN).

Space Complexity: O(1)

Explanation: We are just creating one structure for taking the inputs. It is not considered extra space. Hence SC is O(1)

Frequently asked questions

Q1. What is the difference between a 0/1 knapsack and a fractional knapsack?

Ans. In 0/1 Knapsack, we can either take the item or not; we are not allowed to break the item, while in the case of fractional knapsack, we are allowed to break the items to maximize the profit.  

 

Q2. Can 0/1 Knapsack be solved using the greedy approach?

Ans. No 0/1 knapsack cannot be solved using the greedy approach; it can be solved using a dynamic programming approach. 

 

Q3. What is the greedy approach? 

Ans. It is an algorithm to get the optimal solution for the problem. In this algorithm, we always choose the next best solution that seems optimal at that step. We build solutions piece by piece to reach the optimal solution. 

Key takeaways

In this article, we discussed the classical greedy problem maximum possible value in a knapsack fractional knapsack. We discussed the two approaches, i.e., brute force and optimized approach using the greedy technique. We hope you understand the problem and solution properly. Now you can do more similar questions. 

If you are a beginner, interested in coding, and want to learn DSA, you can look for our guided path for DSA, which is free! 

Thank you for reading. 

Until then, Keep Learning and Keep Coding.

Previous article
Count of unordered pair of indices such that the ratio of elements at these indices is same as the ratio of indices
Next article
Minimize Cash Flow among a given set of friends who have borrowed money from each other
Guided path
Free
gridgp-icon
Competitive programming
16 chapters
217+ Problems
gp-badge
Earn badges and level up
Live masterclass