Greedy algorithm ( Fractional Knapsack problem )
T he greedy algorithm, actually it’s not an algorithm it is a technique with the which we create an algorithm to solve a particular problem. So as its name suggests we have to greedy about the choice that we made, which seems best for that moment, regardless of the fact the choice we made right would turn out to be the worst choice.As
Today we will understand how greedy really works, and how we break items for maximizing the total value of knapsack problem.
First, we have to understand, what is knapsack and what really this knapsack problem is?.
So knapsack means bag. And the problem statement of the knapsack problem is like this…
We have some objects, that you want to import for us to India to sell. And object can be fractional means could be choose in fractional format.If we sell some units of an object in the Indian market we will get some amount of profit form that object
So now as shown in the above image if we sell 18 units of object1, we will get a profit of 25 in the Indian market. The same logic applies to the remaining two objects like for object 2 if weight is 15 units the profit will be 24. But the moment we have reach airport with our objects we came to know that, we have some limitation in luggage transportation at the airport,and we are allowed only to take a bag with us of max 20 units of wight max.
Now we have to arrange objects in our bag in such a way that when we sell the objects in Indian market we will get maximum profit out of it.
So we will try different approaches to solve this problem. Here we will use the greedy technique to find the solution.
- First Approach (Greedy about profit):- First, approach of every single person would be greedy about profit. Since I want to maximize the profits, I will take the objects which can give maximum profit. Therefore it seems, if we take object1 (profit — 25 ) first and put it in the bag, then we would get the max profit right. So after adding, let’s see what happens.
As we can see in the above picture if we took object1 (whose weight is 18 unit and profit of 18 units is 25,) and put it in the bag. Now the weight that remains in the bag is 2 units. So the next item with the maximum profit available is object2 whose profit is 24, only if, we put 15 units of weight. But we don’t have enough space left in the bag.
So if I put 15 u — — — I will get the profit of — — — — 24 of object2
but bag is only left with 2 unit of space
so for 2 u — — — — I will get the profit of — — — — (24/15)*2
So as we went greedy about profit, then after filling the bag completely we have got profit 28.2. So is this the best possible solution?. Or Is there is any other method which we can apply and get the maximum profit out of it. Let’s observe that…
This time we will try to put as many as objects in the bag to maximize the profit. so for that, we will take the object which will be having the least weight, and we should put it first. So that bag would b filled with as many as objects. Therefore this time we are greedy about weights.
2. Second Approach (Greedy about Weight):- This time we have to choose the object with the least weight and that is object3. Therefore we will put object3 first whose weight is 10 as shown in the below
Now after putting object3, the bag still has 10 units of weight remaining. Now next object with the least weight is object2. So now we are going to put object2 in the bag, but we can’t pul all the 15 units of weight because only 10 units of wight are available in the bag. So just like we did before….
So if I put 15 u — — — I will get the profit of — — — — 24 of object2
But if I have only 10 u — — — — I will get the profit of — — — — (24/15)*10
This time we got total profit is 31. This time profit is more than when we were greedy about profits. It is not applicable for all the instances, only for this problem, we are getting more profit if we go greedy for weight rather than greedy for profit.
But still, we are not sure that the last total is the best possible solution to our problem. So what could be other property for which we would be greedy about for maximum profit? So now we won’t either by profits or by weights. This time we will go by the ratio of profit/weight (Fraction Knapsack).
obj1 obj2 obj3
p/w
object 1 — (25/18) = 1.4
object2 — (24/15) =1.6
object3 — (15/10) =1.5
Now we feel that the one with the maximum profit per unit, that has to be placed in the knapsack. So first object to be placed is object2 and then object3 as shown in the below picture.
This time we get the profit is 31.5. This is true for all instances, so whenever we try to find the profit per unit weight ratio and then place the object which has the max p/w ratio. we will always get the maximum profit.
Now we will talk about its algorithm, and also analyze the time complexity .
So above code is the iterative version of the algorithm. One more thing that i want to that if a program can be implement using iteration, we could implement the same program using recursion and vice-versa. But most of the time if we go for recursion we might have to use a recursive stack, because of which space taken for such recursive program might be bigger. Writing a recursive program is simpler but while executing it space taken might me more than to iterative versions.
Let’s implement the algorithm with the following example
m=15 , n=7
Objects 1 2 3 4 5 6 7
Profits 10 5 15 7 6 18 3
Weights 2 3 5 7 1 4 1
now objects are given as shown in the above image and they are saying that (capacity of knapsack is ) m=15 and (number of objects are ) n=7, and every object has profit and weights.
so we will go with the algorithm.
So step 1 of the algorithm is … for i=1 to n, where n means the number of objects. In given example, we have 7 objects. So we have to iterate from 1 to 7 and for each iteration, we have to compute (profit and weight ratio) pi/wi which is step 2 of algo.
Now we will go to step3 of algo, that is sort objects in non-increasing order of p/w like object no (5,1,6,3,7,2,4). also shown in the image7.
Now, step4 is for i=1 to n. { if(m>0)&&wi≤m}
in this we check if (m>0) which means if the knapsack is still having the capacity to hold objects & the chosen object (wi) can completely be placed in the knapsack (wi≤m).
Then step 5 is decrease the capacity of the knapsack with the weight of object i.e m =m-wi, and then increase the total profit by adding profit of weight P=P+pi. if the previous condition is not true step9 is break. and we will check knapsack is still have space and we couldn’t able to put object completely the step10 is we could place the fraction of the profit. So if we go according to the algorithm then first object to add will be like shown below.
as shown in image 7, object5 contains max val of profit and weight ratio(p/w) which is 6.
Step1- Add object 5 in the stack as shown in above image and remove its weight from the total weight of knapsack m=15–1=14. and increse the profi, so P=0+6=6
Step2 — Add object 1 into stack, whose p/w=5, then m= 14-2=12. now toatal profit will be p=6+10=16
Step3 : similary add other objects as shown in the above image till knapsack size become zero i.r m=0.
Step4: When m=0 our profit will be like P=6+10+18+15+3+5*(2/3) = 55.3 (total profit).
Now lets see the time complexity of the algorithm.
from above evaluation we found out that time complexity is O(nlogn).
**Note: Greedy Technique is only feasible in fractional knapSack. where we can divide the entity into fraction . But for 0/1 knapsack we have to go Dynamic Programming. As in 0/1 knapsack we could either take the item or not take the item
Applications of Knapsack :-
- Cognitive Radio Networks
- Resource management in software
- Plastic Bags Waste Management Using the Knapsack Model
Resources
If you want to explore more about fractional knapsack and also from where i have learnt about this technique?. I have listed down some references.
This algorithm is one of the many algorithms that download managers use apart from compressing, encrypting etc etc.
If you like the my hard work and effort, you can do one clap, two clap or may be fourty…
You can also Follow me and WalkIntheCode for more articles like this
You can also find me on..
