+1 vote
1.9k views

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)

1. $40$
2. $38$
3. $32$
4. $30$

recategorized | 1.9k views

 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

by Boss (11k points)
0
If we choose $P_{3}$ first then $P_{4}$ it will also get the same answer.