UGC NET CSE | June 2014 | Part 3 | Question: 62

Question

Consider the fractional knapsack instance

$n = 4, (p_{1} , p_{2} , p_{3} , p_{4} ) = (10, 10, 12, 18), (w_{1} , w_{2} , w_{3} , w_{4} ) = (2, 4, 6, 9)$ and $M = 15$.

The maximum profit is given by (Assume $p$ and $w$ denotes profit and weight of objects respectively)

• A. $40$
• B. $38$ 
• C. $32$
• D. $30$ 

Answer 1

p1/w1	5
p2/w2	2.5
p3/w3	2
p4/w4	2

now select the one which has max(p/w) ratio

that is p1/w1=5 so select 10

next   p2/w2=2.5  select 10

now p3/w3 and p4/w4 has same ratio but p4 gives maximum profit so select p4

therefore the total weight=(2+4+9)=15 and max profit=10+10+18=38

Comments

If we choose $P_{3}$ first then $P_{4}$ it will also get the same answer.

Answer 2

Answer is 38 (pi/wi) is the best approach .