Table of contents | |
Introduction | |
Knapsack Algorithm | |
Algorithm | |
Code Implementation |
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.
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.
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}.
#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.
81 videos|80 docs|33 tests
|
1. What is Fractional Knapsack? |
2. How is the value per unit calculated in Fractional Knapsack? |
3. How is Fractional Knapsack different from 0/1 Knapsack? |
4. What is the time complexity of solving Fractional Knapsack using a greedy algorithm? |
5. How does the greedy approach work in solving Fractional Knapsack? |
|
Explore Courses for Computer Science Engineering (CSE) exam
|