What’s in your Knapsack?

Authors : Amandeep, Drishti, Srinidhi

Hola geeks!!

According to a proverb, it is said that, “If you have figs in your knapsack,everyone will want to be your friend”. But did you know the best algorithm to carry maximum figs in your knapsack? Here’s the post which will help you to!

Fractional Knapsack problem statement

We are given profit and weights of ‘N’ items. We are required to put them in the knapsack having capacity ‘W’ in such a way that it yields maximum total profit. Unlike 0-1 knapsack where we could either take an item or leave it, in fractional knapsack, we can take fractions of an item, thus maximizing our total profit.

Consider the given problem:

Objects	object 1	object 2	object 3
Profit	25	24	15
Weight	18	15	10

Capacity(W)=20

In this problem, 3 cases occur:

1.Greedy about Profit

In this case, we arrange the objects in decreasing order of their profits. Refer the table:

Objects	object 1	object 2	object 3
Profit	25	24	15
Weight	18	15	10

• Soln: 25+2/15 *24 = 28.2

Explanation: As we are greedy about profit,we take object 1 with highest profit and put it in knapsack. Now we are left with capacity 2 (20-18). Hence,we take next highest profit object 2 and take two fractions of it. Thus ,our answer comes out to be 28.2.

2.Greedy about Weight

In this case,we arrange the objects in increasing order of their weights and try to take the minimum weights first. Refer the table:

Objects	object 3	object 2	object 1
Profit	15	24	25
Weights	10	15	18

Soln: 15+10/15*24 = 31

Explanation: As we are greedy about weights,we try to take the minimum weight objects first. Hence, we take profit of object 3 = 15 and now we are left with capacity 10 (20-10). Now we take ten fractions of object 2 making our profit =31.

3.Greedy about Both(optimal solution)

This case gives us the optimal solution for our problem. In this case,we arrange the objects in decreasing order of profit/weight ratio.Refer the table:

Objects	object 2	object 3	object 1
Profit	24	15	25
Weights	15	10	18
Profit/Weight	1.6	1.5	1.3

Soln: 24+5/10*15 = 31.5

Explanation: As we have already arranged the objects according to their Profit/Weight ratio, we choose object 2 with highest P/W ratio and now we are left with capacity 5(20-15). So,we take five fractions of object 3 and the overall profit comes out to be 31.5 which is the highest among all the 3 cases.

Algorithm(optimal Solution)

1.for i=1 to N
  1.1 Calculate Profit/Weight Ratio
2.Sort the objects in decreasing order of Profit/Weight Ratio
3.for i=1 to N
   3.1 if W>0 && w<=W
       3.1.1 W = W - w
       3.1.2 P = P + P(ith)
   3.2 else break 
   3.3 if W>0
      3.3.1 P = P + P(ith)*(W/w)
4.End

Do try analyzing these algorithm, because practice makes perfect! 

For any doubts or ambiguities, mail us at everythinggeeky.101@gmail.com, or comment below! 

Don’t forget to Like, Comment and Share with your friends.

Stay tuned for more interesting and geeky information, right here!

See you next week!

Cheers! 🙂

Team Bitxorbytes

Follow us on instagram:  @bitxorbytes