What is Greedy Method
Before discussing the Fractional Knapsack, we talk a bit about the Greedy Algorithm. Here is our main question is when we can solve a problem with Greedy Method? Each problem has some common characteristic, as like the greedy method has too. Such as if a problem contains those following characteristic , then we can solve this problem using greedy algorithm. Such as
- Maximization or minimization . not twins together
- Problem solution
- Feasible solution
- See elements in each stages
- And finally optimal solution
Look at the name of the method, Greedy Method. That is, we have to solve our problem in a straightforward way so that we can profit. That is, how much we can maximize or minimize when needed.The problem that is given is that there must be a solution.Because without solution, there can be no problem. This problem will have some constraints or limitations. That means we will be given a range beyond which we cannot work.
This Problems will have many feasible solutions. After extracting the feasible solution, we will see each element on each step. At the end, we will find an optimal solution from feasible Solutions.
Note: It is important to remember that one problem may have many optimal solutions and there may not be any optimal solution.
Knapsack means a bag we all know that. In this problem there will have given some profit and weight and also there will be a constraint that I can’t take more weight than that. How we can maximize profit from this restriction is our main task of this problem. Let’s see some equations.Knapsack Equation maximize ᣰPiXi
where 1 <= i <= n
subject to constraints ᣰWiXi <= m
where 1 <= i <= n
0 <= Xi <= 1 and 1 <= i <= n // n here number of object
Look here, Xi is the object whose range you could have understood. If we multiply this object with Profit and find out its summation, we will get the Profit. Now how to maximize this , which is our main task. Look at the next equation we have multiplied the object with weight and given that this weight can’t be bigger than m. But can be equal or smaller. But we won’t take it small. We’ll take Maximum Given weight. ᣰWiXi <= m we need to maximize profits at the base of this limitation. Those solutions that will satisfy these constraints are our feasible solutions.
Note: We’ll work on one data at a time. We cannot take more than one data into a feasible solution. And the object will never be bigger than 1.
Let’s see a problem then all hope will be cleared.
Fractional Knapsack Example With Solution
Knapsack problemn=3 , m=20 , profit (p1,p2,p3)=(25,24,15) and weight (w1,w2,w3)=(18,15,10)
determine the optimal solution of this problem.
First we will sort the data in a descending order. Then it is
profit (p1,p2,p3)=(25,24,15) and weight (w1,w2,w3)=(18,15,10)
object profit weight 1 25 18 2/15 24*2/15 2 0 15 10
Look , first we have taken Object 1, Profit 25 and Weight 18. There is no problem. But the second time we took Weight 2 because we took it 18 before and we know that we can’t take more than 20. So if we take 2 kg out of 15 kg Weight , That’s why the object will be 2/15 and the profit will be 24* 2/15. Since 20 kg is full, so we will take zero the next object. Now after adding profit and weight we will getknapsackProfit = 28.2
Weight = 20
This is our feasible solution.
Note: it’s not the best solution.
This time we will sort the data in ascending order. Then it is
profit (p1,p2,p3)=(15,24,25) and weight (w1,w2,w3)=(10,15,18)
Now see again
object profit weight 1 15 10 10/15 24*10/15 10 0 25 18
Now see if you understand or not. Try it yourself. Here we get Profit 31 and Weight 20.It is also a feasible solution to us because both of them satisfy the constraints .Now we see that this profit is higher than before.
Note: But remember this is not our best solution either.
This way you can extract many feasible solutions. This time we will see how to find an optimal solution.
How to find an optimal solution
We’ll find ratio to get the optimal solution. That mean we will divide profit by weight and then swap in a deciding order. That isKnapsack 25/18=1.38 24/15=1.6 15/10=1.5
Now we get
object profit weight Pi/Wi 1 24 15 1.6 5/10 15*5/10 5 1.5 0 25 18 1.38
Read more Your First Time with Git and Github
Look, whose profit is more , we already took it. That mean 1.6 then 1.5 then 1.38. Adding our profits here will come profit is 31.5 and weight is 20. Look now, the profit is higher than before. This is our best solution.
Note: This is our best solution mechanism
That mean this is our optimal solution.So we will get profit 31.5 for object (1, 5/10, 0). This is our maximum profit here.
We looked at how we can maximize profit from a limitation. This is called Fractional Knapsack.