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

The Gateway to Computer Science Excellence

+1 vote

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)

- $40$
- $38$
- $32$
- $30$

+3 votes

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

52,345 questions

60,517 answers

201,939 comments

95,368 users