Skip to content
GATETECH
Official PYQ · 2018Q48Algorithm Design: Greedy TechniquesNAT2 marks

GATE CS 2018 Q48 — Algorithm Design: Greedy Techniques

Explain with AI
Consider the weights and values of items listed below. Note that there is only one unit of each item.
Item numberWeight (in Kgs) Value (in rupees)11060272834204224\begin{array}{|c|c|c|}\hline \textbf{Item number} & \textbf{Weight (in Kgs) }& \textbf{Value (in rupees)} \\ \hline \text{$1$} & \text{$10$} & \text{$60$} \\ \hline \text{$2$} & \text{$7$} & \text{$28$} \\ \hline \textbf{$3$} & \text{$4$} & \text{$20$} \\ \hline \text{$4$} & \text{$2$} & \text{$24$} \\ \hline \end{array}
The task is to pick a subset of these items such that their total weight is no more than 1111 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 VoptV_{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 VgreedyV_{greedy}.

The value of Vopt−VgreedyV_{opt}-V_{greedy} is ____
View worked solution

Answer: 16

To find the difference Vopt−VgreedyV_{opt} - V_{greedy}, we first compute the value-to-weight ratio for each item and trace both the greedy and optimal strategies for a knapsack capacity of W=11W = 11 Kgs.

Step 1: Calculate Value-to-Weight Ratios

  • Item 1: Ratio = 6010=6.0\frac{60}{10} = 6.0
  • Item 2: Ratio = 287=4.0\frac{28}{7} = 4.0
  • Item 3: Ratio = 204=5.0\frac{20}{4} = 5.0
  • Item 4: Ratio = 242=12.0\frac{24}{2} = 12.0

Sorting the items in descending order of their ratios gives: Item 4, Item 1, Item 3, Item 2.

Step 2: Greedy Algorithm Selection (VgreedyV_{greedy})

  • Pick Item 4 (weight 2, value 24). Remaining capacity = 11−2=911 - 2 = 9.
  • Try Item 1 (weight 10). Since 10>910 > 9, it cannot be picked.
  • Pick Item 3 (weight 4, value 20). Remaining capacity = 9−4=59 - 4 = 5.
  • Try Item 2 (weight 7). Since 7>57 > 5, it cannot be picked.

Thus, the greedy algorithm picks {Item 4, Item 3} with total value:
Vgreedy=24+20=44V_{greedy} = 24 + 20 = 44

Step 3: Optimal Selection (VoptV_{opt})

We find the subset of items whose total weight is ≤11\le 11 and maximizes the total value:

  • Subset {Item 1}: Weight = 10, Value = 60
  • Subset {Item 2, Item 3}: Weight = 11, Value = 48
  • Subset {Item 2, Item 4}: Weight = 9, Value = 52

The maximum value is obtained by picking only Item 1, giving:
Vopt=60V_{opt} = 60

Step 4: Difference

Vopt−Vgreedy=60−44=16V_{opt} - V_{greedy} = 60 - 44 = 16

Free practice · Your answers on this page are not saved.

Published
Report a correction
Keep exploringMore Algorithm Design: Greedy Techniques questions