Consider the fractional knapsack instance n = 4, (p1 , p2 , p3 , p4 ) = (10,…
2014
Consider the fractional knapsack instance n = 4, (p1 , p2 , p3 , p4 ) = (10, 10, 12, 18), (w1 , w2 , w3 , w4) = (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
Attempted by 240 students.
Show answer & explanation
Correct answer: B
Solution: Use the greedy strategy by profit-per-weight (profit/weight).
Compute profit-per-weight for each object:
Object 1: profit 10, weight 2, ratio = 5
Object 2: profit 10, weight 4, ratio = 2.5
Object 3: profit 12, weight 6, ratio = 2
Object 4: profit 18, weight 9, ratio = 2
Order by decreasing ratio: Object 1, Object 2, then Objects 3 and 4 (tie).
Take Object 1 completely: weight 2, profit +10. Remaining capacity = 13.
Take Object 2 completely: weight 4, profit +10. Remaining capacity = 9.
Take Object 3 completely: weight 6, profit +12. Remaining capacity = 3.
Take a fraction of Object 4 to fill remaining capacity: take 3/9 of Object 4 giving profit 18 * (3/9) = 6.
Total profit = 10 + 10 + 12 + 6 = 38.
Maximum profit = 38.