retagged by
1,971 views

1 Answer

Best answer
5 votes
5 votes

In case of fractional knapsack we apply greedy technique.We calculate Pi / Wi for each item 

So,

P/ W1   =   70 / 10 = 7

P2 / W2   =   25 / 1   = 25

P3 / W3   =   15 / 2 =  7.5

P/ W4   =    29 / 2  = 14.5

P5 / W5   =   38 / 6  =  6.33

So now we select the processes giving priority to one having larger profit by weight ratio.

So P2   is selected first 

Profit  =  25    

Weight remaining = 14 - 1 = 13

Then P4 is selected , so 

profit  = 25 + 29  = 54

weight remaining  = 13 - 2 = 11

Then P3 is selected 

So profit  = 54 + 15  = 69

weight remaining  = 11 - 2 = 9

Then P1 is selected .

But remaining weight = 9 and its weight = 10 , so we consider the profit of (9/10) th part only

So profit    =    69 + 9/10 * 70

                =    69 + 63

                =    132

Hence maximum profit achievable using fractional knapsack = 132

selected by

Related questions

1 votes
1 votes
1 answer
1
Aradhana Singh asked Oct 25, 2016
572 views
what is the difference between fractional knapsack and 0-1 problem . pl explain concepts with simple problems
0 votes
0 votes
1 answer
2
Parshu gate asked Nov 16, 2017
8,212 views
The following Knapsack bag. The Knapsack bag maximum Capacity is 50. Find out the maximum profit for Fractional Knapsack. PQRSTUVWWeight1812161416201015Profit341522161722...
0 votes
0 votes
1 answer
3
LavTheRawkstar asked Apr 15, 2017
3,873 views
Consider the following instance of the knapsack problem: n=3 , W=50 , (v1,v2,v3) = (60,100,120) and weight (w1,w2,w3) = (10,20,30) .solve the given knapsack problem apply...
0 votes
0 votes
1 answer
4
LavTheRawkstar asked Feb 28, 2017
12,832 views
Consider the Knapsack incidence with n=3(items) with weights {w1,w2,w3}={2,3,4} and profits are {p1,p2,p3}={1,2,5}Given the capacity is 5,{W/M = 5 } Find the optimal solu...