The Gateway to Computer Science Excellence
+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$ 
in Algorithms by Boss (30.1k points)
recategorized by | 1.9k views

1 Answer

+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

by Boss (11k points)
0
If we choose $P_{3}$ first then $P_{4}$ it will also get the same answer.
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,648 questions
56,430 answers
195,212 comments
99,927 users