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
- Sort the array in decreasing order using the value/weight ratio.
- Start taking the element having the maximum value/weight ratio.
- 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.
- Stop adding the elements when the capacity of the knapsack becomes 0
- 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;
}
You can also try this code with Online C++ Compiler
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.
130+ registered 
