GATE CS 2018 Q.58 (CS Q.48): Dynamic Programming

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_{\text{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 $V_{\text{greedy}}$ .

The value of $V_{\text{opt}} - V_{\text{greedy}}$ is ____________.

Your answer

Official answer and solution

Official answer: 16
From: Official GATE 2018 answer key

Solution

Compute the greedy selection based on value-to-weight ratios and compare it with the exact 0/1 knapsack optimum.

Compute value-to-weight ratios for all items:

Item 1: $w = 10, v = 60 \implies \text{ratio} = 60/10 = 6.0$
Item 2: $w = 7, v = 28 \implies \text{ratio} = 28/7 = 4.0$
Item 3: $w = 4, v = 20 \implies \text{ratio} = 20/4 = 5.0$
Item 4: $w = 2, v = 24 \implies \text{ratio} = 24/2 = 12.0$

Greedy packing (sorted by ratio descending: Item 4, Item 1, Item 3, Item 2):

Pick Item 4: weight = 2, value = 24, capacity remaining = $11 - 2 = 9$ .
Next is Item 1: weight = 10. Since $10 > 9$ , cannot pack Item 1.
Next is Item 3: weight = 4. Since $4 \le 9$ , pack Item 3: value becomes $24 + 20 = 44$ , capacity remaining = $9 - 4 = 5$ .
Next is Item 2: weight = 7. Since $7 > 5$ , cannot pack Item 2.
Thus, $V_{\text{greedy}} = 44$ .

Optimal 0/1 knapsack ( $W = 11$ ):

Item 1 alone: weight = 10, value = 60.
Items 2 and 3: weight = $7 + 4 = 11$ , value = $28 + 20 = 48$ .
Items 2 and 4: weight = $7 + 2 = 9$ , value = $28 + 24 = 52$ .
Items 3 and 4: weight = $4 + 2 = 6$ , value = $20 + 24 = 44$ .
The maximum achievable value is $V_{\text{opt}} = 60$ .

Compute difference:

V_{\text{opt}} - V_{\text{greedy}} = 60 - 44 = 16

Final answer

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2018 Computer Science and Information Technology (CS)
Question: 58 of 65, printed as CS Q.48
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source