The GATE Grind

GATE 2021 CS (CS1) – Question 50

Algorithms · Dynamic Programming · 2 marks · Multiple select

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$?

  1. $R_7 = 18$
  2. $R_7 = 19$
  3. $R_7$ is achieved by three different solutions.
  4. $R_7$ cannot be achieved by a solution consisting of three pieces.

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.

More Dynamic Programming questions

All Dynamic Programming questions →