Last Updated on March 30, 2022 by Ria Pathak
CONCEPTS USED:
Greedy algorithm(fractional knapsack)
DIFFICULTY LEVEL:
Medium
PROBLEM STATEMENT(SIMPLIFIED):
One day some guests came to Aman’s home. Aman’s mama told him to bring N items from the market and gave him a bag, but the bag can hold a maximum weight of W units. Every item has some weight wi and a value vi. Aman has to put these items in the bag such that the total value is maximized.
Note: Aman can break items for maximizing the total value of the bag.
See original problem statement here
For Example :
3 30
30 8
40 5
60 20
121
Aman chooses item 2 ,item 1 and 17 g of item 3 (40+30+3*17=121)OBSERVATION:
Since the items can be broken ,the key point in this question is the value / unit mass of the item!!
SOLVING APPROACH:
BRUTE FORCE:
Try all different subsets that can be formed for the given weight.But that will take exponential time.
GREEDY APPROACH:
What we’ll do is while the bag is still not full, we will do a greedy choice. We will choose the item number i which has the maximum value of vi over wi, which is the value per unit of weight. And then if this item fits into bag fully, then take off all this item. Otherwise, if there is only few spaces left in the bag, take so much of this item as to fill the bag to the end. And then, in the end, we’ll return the total value of the items that we took and how much did we take off each item.
sort all the items in decreasing order of their value / weight ratio.
Start putting the items into the bag beginning from the item with the highest ratio.
Put as many items as you can into the knapsack.
Time complexity: The main time taking step is the sorting of all items in decreasing order of their value / weight ratio.
SOLUTIONS:
# include<stdio.h>
void knapsack(int n, float weight[], float profit[], float capacity) {
float x[n], tp = 0;
int i, j, u;
u = capacity;
for (i = 0; i < n; i++)
x[i] = 0.0;
for (i = 0; i < n; i++) {
if (weight[i] > u)
break;
else {
x[i] = 1.0;
tp = tp + profit[i];
u = u - weight[i];
}
}
if (i < n)
x[i] = u / weight[i];
tp = tp + (x[i] * profit[i]);
int ans=round(tp);
printf("%d", ans);
}
int main() {
int num, i, j;
float temp,capacity;
scanf("%d", &num);
scanf("%f", &capacity);
float weight[num], profit[num],ratio[num] ;
for (i = 0; i < num; i++) {
scanf("%f %f", &profit[i], &weight[i]);
}
for (i = 0; i < num; i++) {
ratio[i] = profit[i] / weight[i];
}
for (i = 0; i < num; i++) {
for (j = i + 1; j < num; j++) {
if (ratio[i] < ratio[j]) {
temp = ratio[j];
ratio[j] = ratio[i];
ratio[i] = temp;
temp = weight[j];
weight[j] = weight[i];
weight[i] = temp;
temp = profit[j];
profit[j] = profit[i];
profit[i] = temp;
}
}
}
knapsack(num, weight, profit, capacity);
return(0);
}
#include <bits/stdc++.h>
using namespace std;
bool comp(pair<int, int> a, pair<int, int> b)
{
return (double)a.first/ a.second >
(double)b.first/ b.second;
}
double fractionalKnapsack(int W,pair<int, int>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].second <= W)
{
curWeight += arr[i].second;
finalvalue += arr[i].first;
}
else
{
int remain = W - curWeight;
finalvalue += arr[i].first * ((double) remain / arr[i].second);
break;
}
}
return finalvalue;
}
int main()
{
int n,w;
cin>>n>>w;
pair<int ,int> p[n];
for(int i=0;i<n;i++)
cin>>p[i].first>>p[i].second;
cout<<lround(fractionalKnapsack(w, p, n));
return 0;
}
import java.util.*;
//import java.io.*;
import java.util.Arrays;
import java.util.Comparator;
class FractionalKnapSack
{
public static void main(String[] args)
{ Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int capacity = sc.nextInt();
int p[]=new int[n];
int a[]=new int[n];
for(int i=0;i<n;i++)
{
p[i] = sc.nextInt();
a[i] = sc.nextInt();
}
double maxValue = getMaxValue(a, p, capacity);
System.out.println(maxValue);
}
private static double getMaxValue(int[] wt,
int[] val, int capacity)
{
ItemValue[] iVal = new ItemValue[wt.length];
for(int i = 0; i < wt.length; i++)
{
iVal[i] = new ItemValue(wt[i], val[i], i);
}
Arrays.sort(iVal, new Comparator<ItemValue>()
{
@Override
public int compare(ItemValue o1, ItemValue o2)
{
return o2.cost.compareTo(o1.cost) ;
}
});
double totalValue = 0d;
for(ItemValue i: iVal)
{
int curWt = (int) i.wt;
int curVal = (int) i.val;
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
{
Double cost;
double wt, val, ind;
public ItemValue(int wt, int val, int ind)
{
this.wt = wt;
this.val = val;
this.ind = ind;
cost = new Double(val/wt );
}
}
}
[forminator_quiz id="1451"]
This article tried to discuss the concept of Greedy algorithm. Hope this blog helps you understand and solve the problem. To practice more problems on Greedy algorithm you can check out MYCODE | Competitive Programming.