Consider the weights and values of items listed below. Note that there is only…
2018
Consider the weights and values of items listed below. Note that there is only one unit of each item.
The task is to pick a subset of these items such that their total weight is no more than 11 Kgs and their total value is maximized. Moreover, no item may be split. The total value of items picked by an optimal algorithm is denoted by 𝑉opt. A greedy algorithm sorts the items by their value-to-weight ratios in descending order and packs them greedily, starting from the first item in the ordered list. The total value of items picked by the greedy algorithm is denoted by 𝑉greedy.
The value of 𝑉opt − 𝑉greedy is ____________.
Attempted by 112 students.
Show answer & explanation
Correct answer: 16
Key insight: compute value-to-weight ratios, simulate the greedy packing, and compare with the best feasible subset under the 11 Kg limit.
Compute value-to-weight ratios: Item 1 — weight 10, value 60, ratio 6; Item 2 — weight 7, value 28, ratio 4; Item 3 — weight 4, value 20, ratio 5; Item 4 — weight 2, value 24, ratio 12.
Greedy order (descending ratio): Item 4, Item 1, Item 3, Item 2.
Greedy packing simulation: pick Item 4 (w=2, v=24), remaining capacity 9; skip Item 1 (w=10 doesn't fit); pick Item 3 (w=4, v=20), remaining capacity 5; Item 2 doesn't fit. Greedy total value = 24 + 20 = 44.
Check best feasible subsets under 11 Kg: Item 1 alone gives value 60 (w=10). Other feasible combos give at most 52 (Items 2+4) or 48 (Items 2+3), so the optimal value is 60.
Therefore Vopt = 60 and Vgreedy = 44, so Vopt − Vgreedy = 16.
A video solution is available for this question — log in and enroll to watch it.