Greedy Algorithm | Fractional Knapsack Problem With Solution

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

1. Maximization or minimization . not twins together   
2. Problem solution
3. Constraints 
4. Requirements 
5. Feasible solution 
6. See elements in each stages 
7. 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. 

Fractional Knapsack

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.

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 

solution

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)

Now see

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 get

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 is

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.