GATE CS 2021 Set 1 Q40 — Algorithm Design: Greedy Techniques

Using the dynamic programming approach for the rod cutting problem, the maximum revenue $R_n$ for a rod of length $n$ is given by:

Let's compute $R_i$ step-by-step for $i = 1$ to $7$:

• $R_1 = p[1] = 1$
• $R_2 = \max(p[2], p[1] + R_1) = \max(5, 1 + 1) = 5$
• $R_3 = \max(p[3], p[1] + R_2, p[2] + R_1) = \max(8, 1 + 5, 5 + 1) = 8$
• $R_4 = \max(p[4], p[1] + R_3, p[2] + R_2, p[3] + R_1) = \max(9, 1 + 8, 5 + 5, 8 + 1) = 10$
• $R_5 = \max(p[5], p[1] + R_4, p[2] + R_3, p[3] + R_2, p[4] + R_1) = \max(10, 1 + 10, 5 + 8, 8 + 5, 9 + 1) = 13$
• $R_6 = \max(p[6], p[1] + R_5, p[2] + R_4, p[3] + R_3, p[4] + R_2, p[5] + R_1) = \max(17, 1 + 13, 5 + 10, 8 + 8, 9 + 5, 10 + 1) = 17$
• $R_7 = \max(p[7], p[1] + R_6, p[2] + R_5, p[3] + R_4, p[4] + R_3, p[5] + R_2, p[6] + R_1) = \max(18, 18, 18, 18, 17, 15, 18) = 18$

Thus, $R_7 = 18$. This makes Statement A correct and Statement B incorrect.

Now, let's identify all partitions of length $7$ that yield a total revenue of $18$:

1. 1 piece: $\{7\}$ with revenue $p[7] = 18$
2. 2 pieces: $\{6, 1\}$ with revenue $p[6] + p[1] = 17 + 1 = 18$
3. 3 pieces: $\{3, 2, 2\}$ with revenue $p[3] + p[2] + p[2] = 8 + 5 + 5 = 18$

Since there are exactly three different solutions that achieve $R_7 = 18$, Statement C is correct. Because one of these solutions consists of three pieces, Statement D is incorrect.