Define \(R_n\) to be the maximum amount earned by cutting a rod of length n…

2021

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:

\(\text{p}[1]=1,\text{p}[2]=5,\text{p}[3]=8,\text{p}[4]=9,\text{p}[5]=10,\text{p}[6]=17,\text{p}[7]=18\)

Which of the following statements is/are correct about \(R_7\) ?

  1. A.

    \(R_7\) = 18

  2. B.

    \(R_7\) = 19

  3. C.

    \(R_7\) is achieved by three different solutions.

  4. D.

    \(R_7\) cannot be achieved by a solution consisting of three pieces.

Attempted by 30 students.

Show answer & explanation

Correct answer: A, C

Use the recurrence R_n = max_{1<=i<=n} (p[i] + R_{n-i}) with R_0 = 0 to compute maximum revenues for lengths 1 through 7.

  • R1 = max(p1) = 1

  • R2 = max(p2 = 5, p1 + R1 = 1 + 1 = 2) = 5

  • R3 = max(p3 = 8, p1 + R2 = 1 + 5 = 6, p2 + R1 = 5 + 1 = 6) = 8

  • R4 = max(p4 = 9, p1 + R3 = 1 + 8 = 9, p2 + R2 = 5 + 5 = 10, p3 + R1 = 8 + 1 = 9) = 10

  • R5 = max(p5 = 10, p1 + R4 = 1 + 10 = 11, p2 + R3 = 5 + 8 = 13, p3 + R2 = 8 + 5 = 13, p4 + R1 = 9 + 1 = 10) = 13

  • R6 = max(p6 = 17, p1 + R5 = 1 + 13 = 14, p2 + R4 = 5 + 10 = 15, p3 + R3 = 8 + 8 = 16, p4 + R2 = 9 + 5 = 14, p5 + R1 = 10 + 1 = 11) = 17

  • R7 = max(p7 = 18, p1 + R6 = 1 + 17 = 18, p2 + R5 = 5 + 13 = 18, p3 + R4 = 8 + 10 = 18, p4 + R3 = 9 + 8 = 17, p5 + R2 = 10 + 5 = 15, p6 + R1 = 17 + 1 = 18) = 18

Therefore the maximum revenue for length 7 is 18.

All distinct partitions (ignoring order) that achieve R7 = 18 are:

  • Sell length 7 as a whole: 7 -> p7 = 18

  • Cut into lengths 1 and 6: p1 + p6 = 1 + 17 = 18

  • Cut into lengths 2, 2, and 3: p2 + p2 + p3 = 5 + 5 + 8 = 18

Conclusions about the statements in the question:

  • The statement that R7 = 18 is correct.

  • The statement that R7 = 19 is incorrect; no combination yields 19.

  • The statement that R7 is achieved by three different solutions is correct; the three distinct partitions are listed above.

  • The statement that R7 cannot be achieved by a solution consisting of three pieces is incorrect; 2 + 2 + 3 is a three-piece solution achieving 18.

Explore the full course: Gate Guidance By Sanchit Sir