Fractional Knapsack Problem
Last Updated :
03 Apr, 2023
Given the weights and profits of N items, in the form of {profit, weight} put these items in a knapsack of capacity W to get the maximum total profit in the knapsack. In Fractional Knapsack, we can break items for maximizing the total value of the knapsack.
Input: arr[] = {{60, 10}, {100, 20}, {120, 30}}, W = 50
Output: 240
Explanation: By taking items of weight 10 and 20 kg and 2/3 fraction of 30 kg.
Hence total price will be 60+100+(2/3)(120) = 240
Input: arr[] = {{500, 30}}, W = 10
Output: 166.667
Naive Approach: To solve the problem follow the below idea:
Try all possible subsets with all different fractions.
Time Complexity: O(2N)
Auxiliary Space: O(N)
Fractional Knapsack Problem using Greedy algorithm:
An efficient solution is to use the Greedy approach.
The basic idea of the greedy approach is to calculate the ratio profit/weight for each item and sort the item on the basis of this ratio. Then take the item with the highest ratio and add them as much as we can (can be the whole element or a fraction of it).
This will always give the maximum profit because, in each step it adds an element such that this is the maximum possible profit for that much weight.
Illustration:
Check the below illustration for a better understanding:
Consider the example: arr[] = {{100, 20}, {60, 10}, {120, 30}}, W = 50.
Sorting: Initially sort the array based on the profit/weight ratio. The sorted array will be {{60, 10}, {100, 20}, {120, 30}}.
Iteration:
- For i = 0, weight = 10 which is less than W. So add this element in the knapsack. profit = 60 and remaining W = 50 – 10 = 40.
- For i = 1, weight = 20 which is less than W. So add this element too. profit = 60 + 100 = 160 and remaining W = 40 – 20 = 20.
- For i = 2, weight = 30 is greater than W. So add 20/30 fraction = 2/3 fraction of the element. Therefore profit = 2/3 * 120 + 160 = 80 + 160 = 240 and remaining W becomes 0.
So the final profit becomes 240 for W = 50.
Follow the given steps to solve the problem using the above approach:
- Calculate the ratio (profit/weight) for each item.
- Sort all the items in decreasing order of the ratio.
- Initialize res = 0, curr_cap = given_cap.
- Do the following for every item i in the sorted order:
- If the weight of the current item is less than or equal to the remaining capacity then add the value of that item into the result
- Else add the current item as much as we can and break out of the loop.
- Return res.
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h>
using namespace std;
struct Item {
int profit, weight;
Item(int profit, int weight)
{
this->profit = profit;
this->weight = weight;
}
};
static bool cmp(struct Item a, struct Item b)
{
double r1 = (double)a.profit / (double)a.weight;
double r2 = (double)b.profit / (double)b.weight;
return r1 > r2;
}
double fractionalKnapsack(int W, struct Item arr[], int N)
{
sort(arr, arr + N, cmp);
double finalvalue = 0.0;
for (int i = 0; i < N; i++) {
if (arr[i].weight <= W) {
W -= arr[i].weight;
finalvalue += arr[i].profit;
}
else {
finalvalue
+= arr[i].profit
* ((double)W / (double)arr[i].weight);
break;
}
}
return finalvalue;
}
int main()
{
int W = 50;
Item arr[] = { { 60, 10 }, { 100, 20 }, { 120, 30 } };
int N = sizeof(arr) / sizeof(arr[0]);
cout << fractionalKnapsack(W, arr, N);
return 0;
}
|
Java
import java.lang.*;
import java.util.Arrays;
import java.util.Comparator;
public class FractionalKnapSack {
private static double getMaxValue(ItemValue[] arr,
int capacity)
{
Arrays.sort(arr, new Comparator<ItemValue>() {
@Override
public int compare(ItemValue item1,
ItemValue item2)
{
double cpr1
= new Double((double)item1.profit
/ (double)item1.weight);
double cpr2
= new Double((double)item2.profit
/ (double)item2.weight);
if (cpr1 < cpr2)
return 1;
else
return -1;
}
});
double totalValue = 0d;
for (ItemValue i : arr) {
int curWt = (int)i.weight;
int curVal = (int)i.profit;
if (capacity - curWt >= 0) {
capacity = capacity - curWt;
totalValue += curVal;
}
else {
double fraction
= ((double)capacity / (double)curWt);
totalValue += (curVal * fraction);
capacity
= (int)(capacity - (curWt * fraction));
break;
}
}
return totalValue;
}
static class ItemValue {
int profit, weight;
public ItemValue(int val, int wt)
{
this.weight = wt;
this.profit = val;
}
}
public static void main(String[] args)
{
ItemValue[] arr = { new ItemValue(60, 10),
new ItemValue(100, 20),
new ItemValue(120, 30) };
int capacity = 50;
double maxValue = getMaxValue(arr, capacity);
System.out.println(maxValue);
}
}
|
Python3
class Item:
def __init__(self, profit, weight):
self.profit = profit
self.weight = weight
def fractionalKnapsack(W, arr):
arr.sort(key=lambda x: (x.profit/x.weight), reverse=True)
finalvalue = 0.0
for item in arr:
if item.weight <= W:
W -= item.weight
finalvalue += item.profit
else:
finalvalue += item.profit * W / item.weight
break
return finalvalue
if __name__ == "__main__":
W = 50
arr = [Item(60, 10), Item(100, 20), Item(120, 30)]
max_val = fractionalKnapsack(W, arr)
print(max_val)
|
C#
using System;
using System.Collections;
class GFG {
class item {
public int profit;
public int weight;
public item(int profit, int weight)
{
this.profit = profit;
this.weight = weight;
}
}
class cprCompare : IComparer {
public int Compare(Object x, Object y)
{
item item1 = (item)x;
item item2 = (item)y;
double cpr1 = (double)item1.profit
/ (double)item1.weight;
double cpr2 = (double)item2.profit
/ (double)item2.weight;
if (cpr1 < cpr2)
return 1;
return cpr1 > cpr2 ? -1 : 0;
}
}
static double FracKnapSack(item[] items, int w)
{
cprCompare cmp = new cprCompare();
Array.Sort(items, cmp);
double totalVal = 0f;
int currW = 0;
foreach(item i in items)
{
float remaining = w - currW;
if (i.weight <= remaining) {
totalVal += (double)i.profit;
currW += i.weight;
}
else {
if (remaining == 0)
break;
double fraction
= remaining / (double)i.weight;
totalVal += fraction * (double)i.profit;
currW += (int)(fraction * (double)i.weight);
}
}
return totalVal;
}
static void Main(string[] args)
{
int W = 50;
item[] arr = { new item(60, 10), new item(100, 20),
new item(120, 30) };
Console.WriteLine(FracKnapSack(arr, W));
}
}
|
Javascript
class Item {
constructor(profit, weight) {
this.profit = profit;
this.weight = weight;
}
}
function cmp(a, b) {
let r1 = a.profit / a.weight;
let r2 = b.profit / b.weight;
return r1 > r2;
}
function fractionalKnapsack(W, arr) {
arr.sort(cmp);
let finalvalue = 0.0;
for (let i = 0; i < arr.length; i++) {
if (arr[i].weight <= W) {
W -= arr[i].weight;
finalvalue += arr[i].profit;
}
else {
finalvalue += arr[i].profit * (W / arr[i].weight);
break;
}
}
return finalvalue;
}
let W = 50;
let arr = [new Item(60, 10), new Item(100, 20), new Item(120, 30)];
console.log(fractionalKnapsack(W, arr));
|
Time Complexity: O(N * logN)
Auxiliary Space: O(N)