The GATE Grind

GATE 2021 CS – 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

R7 = 18, achieved by {7}, {1,6} (1+17) and {2,2,3} (5+5+8). So there are three solutions, one of which has three pieces; 19 is not attainable.