GATE 2021 CS (CS1) – Question 50
Define $R_n$ to be the maximum amount earned by cutting a rod of length $n$ meters into one or more pieces of integer length and selling them. For $i>0$, let $p[i]$ denote the selling price of a rod whose length is $i$ meters. Consider the array of prices: p[1]=1, p[2]=5, p[3]=8, p[4]=9, p[5]=10, p[6]=17, p[7]=18. Which of the following statements is/are correct about $R_7$?
Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: (A) $R_7 = 18$; (C) $R_7$ is achieved by three different solutions.
Explanation
Prices: $p_1=1,\ p_2=5,\ p_3=8,\ p_4=9,\ p_5=10,\ p_6=17,\ p_7=18$.
Use $R_n=\max_{1\le i\le n}(p_i+R_{n-i})$, $R_0=0$:
- $R_1=1$
- $R_2=\max(1+1,\ 5)=5$
- $R_3=\max(5+1,\ 1+5,\ 8)=8$
- $R_4=\max(9,\ 8+1,\ 5+5,\ 1+8)=10$
- $R_5=\max(10,\ 9+1,\ 8+5,\ 5+8,\ 1+10)=13$
- $R_6=\max(17,\ 10+1,\ 9+5,\ 8+8,\ 5+10,\ 1+13)=17$
- $R_7=\max(18,\ 17+1,\ 10+5,\ 9+8,\ 8+10,\ 5+13,\ 1+17)=18$
**(A)** $R_7=18$: true; **(B)** 19: false.
**Optimal solutions for $R_7=18$:** $\{7\}$ ($18$), $\{1,6\}$ ($1+17$) and $\{2,2,3\}$ ($5+5+8$). That is **three** different solutions, so **(C)** is true. One of them, $\{2,2,3\}$, has three pieces, so **(D)** is false.
Answer: A, C.