Consider the fractional knapsack instance n = 4, (p₁, p₂, p₃, p₄) = (10, 10, 12, 18), (w₁, w₂, w₃, w₄) = (2, 4, 6, 9) and M = 15. The maximum profit is…
Consider the fractional knapsack instance n = 4, (p₁, p₂, p₃, p₄) = (10, 10, 12, 18), (w₁, w₂, w₃, w₄) = (2, 4, 6, 9) and M = 15. The maximum profit is given by (Assume p and w denotes profit and weight of objects respectively)
Show answerHide answer
Correct answer: (B) 38
Explanation
P₁/w₁ = 5, p₂/w₂ = 2.5, p₃/w₃ = 2, p₄/w₄ = 2. Select object 1 (profit 10), then object 2 (profit 10). Objects 3 and 4 have the same ratio, but object 4 gives more profit and fits exactly: total weight = 2 + 4 + 9 = 15. Maximum profit = 10 + 10 + 18 = 38. So the answer is (b).