GATE CS 2014 Set 1 Q37 — Algorithm Design: Greedy Techniques

Let $x_i \in \{0, 1\}$ represent whether bag $i$ contains $11$ gm coins ($x_i = 1$) or $10$ gm coins ($x_i = 0$) for $i \in \{1, 2, 3, 4, 5\}$.

The number of coins picked from bags $1, 2, 3, 4,$ and $5$ are $1, 2, 4, 8,$ and $16$ respectively. The total number of coins picked is:

If all bags contained $10$ gm coins, the total weight would be:

The actual total weight is $323$ gm. The excess weight is due to the bags containing $11$ gm coins, where each coin contributes an extra $1$ gm:

We can express this excess weight as a sum of the powers of $2$ corresponding to the number of coins picked from each bag:

Since $x_i \in \{0, 1\}$, this is equivalent to finding the binary representation of $13$:

Comparing the coefficients, we get:

• $x_1 = 1$ (Bag 1 has $11$ gm coins)
• $x_2 = 0$
• $x_3 = 1$ (Bag 3 has $11$ gm coins)
• $x_4 = 1$ (Bag 4 has $11$ gm coins)
• $x_5 = 0$

The bags containing $11$ gm coins are 1, 3, and 4.

The product of these labels is: