GATE 2018 CS Q.48: solution and answer

GATE 2018 · CSQ.48 · 2 marks · NAT

Consider the weights and values of items listed below. Note that there is only one unit of each item.

| Item number | Weight (in Kgs) | Value (in Rupees) |
|---|---|---|
| 1 | 10 | 60 |
| 2 | 7 | 28 |
| 3 | 4 | 20 |
| 4 | 2 | 24 |

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 $V_{o pt}$ . 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 $V_{g r ee d y}$ .

The value of $V_{o pt} - V_{g r ee d y}$ is ____________.

See the question in the paper

Tap to open full size

Answer and solution

ANSWER

V_opt − V_greedy = 60 − 44 = 16

Official answer: 16Source: Official answer key, GATE 2018 CS (IIT Guwahati)

Ratio (value/weight) for each item: item1 = 60/10 = 6, item2 = 28/7 = 4, item3 = 20/4 = 5, item4 = 24/2 = 12.
Greedy order (ratio descending): item4 (12), item1 (6), item3 (5), item2 (4).
Greedy packing with capacity 11 Kg, considering items in this order and adding an item only if it still fits in the remaining capacity: take item4 (w=2, v=24), remaining capacity = 9; item1 needs w=10 > 9, so skip it; item3 needs w=4 ≤ 9, take it, remaining capacity = 5, total so far w=6, v=44; item2 needs w=7 > 5, so skip it.
$V_{g r ee d y} = 24 + 20 = 44$ (total weight used = 6 Kg out of 11 Kg allowed).
For $V_{o pt}$ , check every subset with total weight $\leq 11$ Kg: ${1}$ (w=10, v=60), ${2}$ (w=7, v=28), ${3}$ (w=4, v=20), ${4}$ (w=2, v=24), ${2, 3}$ (w=11, v=48), ${2, 4}$ (w=9, v=52), ${3, 4}$ (w=6, v=44); every 3-item or 4-item combination exceeds 11 Kg.
The best feasible subset is ${1}$ alone, giving $V_{o pt} = 60$ .
$V_{o pt} - V_{g r ee d y} = 60 - 44 = 16$ .

KEY IDEA

Compute $V_{g r ee d y}$ by sorting items on value-to-weight ratio and greedily adding any item (in ratio order) that still fits in the remaining capacity, skipping only the ones that don't; separately compute $V_{o pt}$ by exhaustively checking every subset with total weight $\leq 11$ Kg, since $n = 4$ is small enough for brute force. The gap $V_{o pt} - V_{g r ee d y}$ is the classic illustration that the greedy ratio heuristic is not optimal for 0/1 knapsack.

WATCH OUT FOR

Stopping the greedy pass as soon as one item fails to fit (instead of continuing to check the remaining, lower-ratio items against the leftover capacity), or restricting the "optimal" search to combinations that happen to look greedy-adjacent instead of checking all $2^{4}$ subsets — both shortcuts miss that the single item {1} (weight 10, value 60) alone beats every combination the greedy method can reach.

From the GATE 2018 CS paper. Every question of this paper · Download the full paper · All 8 Design techniques questions, with notes

GATE 2018 CS Q.48: solution and answer

Answer and solution

More Design techniques questions