The Gateway to Computer Science Excellence
0 votes
777 views

in Algorithms by Active (4.9k points) | 777 views
+1
(25+29+15+63(9 out of 10 used ))= 132

1 Answer

+5 votes
Best answer

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

by Veteran (101k points)
selected by
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,666 questions
56,157 answers
193,767 comments
93,752 users