# 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

**Maximization or minimization . not twins together****Problem solution****Constraints****Requirements****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.

**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.

## Knapsack Equation

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 problem

determine the optimal solution of this problem.

**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

## knapsack

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 is

## Knapsack

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.

**Codechief** is a very fast growing community among programmers and have a reach of around 1 million+ readers globally. Contribution at **Codechief** is open for all those who have a passion to learn and help others by sharing their knowledge. If you think you have the zeal to learn, start contributing on **Codechief **contribute.
you can also mail your article to **[email protected]** See your article appearing on the codechief main page and help other code.

We believe that everyone has the right to learn, so we allow both students and professionals to contribute on **Codechief**.Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.

Was this article helpful?