GATE CS 2021 Set 1 Q.50 (CS Q.40): Dynamic Programming

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, \quad p[2] = 5, \quad p[3] = 8, \quad p[4] = 9, \quad p[5] = 10, \quad p[6] = 17, \quad p[7] = 18

Which of the following statements is/are correct about $R_7$ ?

$R_7 = 18$

$R_7 = 19$

$R_7$ is achieved by three different solutions.

$R_7$ cannot be achieved by a solution consisting of three pieces.

Official answer and solution

Official answer: A and C
From: Official GATE 2021 answer key

Solution

Compute optimal revenue for rod lengths 1 through 7 using dynamic programming, and list all combinations that achieve the maximum.

The price array is: $p[1]=1, p[2]=5, p[3]=8, p[4]=9, p[5]=10, p[6]=17, p[7]=18$ .
The dynamic programming recurrence is $R_n = \max_{1 \le i \le n} (p[i] + R_{n-i})$ , with $R_0 = 0$ .

Compute bottom-up:

$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, 1+17, 5+13, 8+10, 9+8, 10+5, 17+1) = 18$

Thus $R_7 = 18$ (Statement A is correct, B is false).
Now find all partitions of 7 yielding revenue 18:

Cut into 1 piece: $7 \implies p[7] = 18$ .
Cut into 2 pieces: $1 + 6 \implies p[1] + p[6] = 1 + 17 = 18$ .
Cut into 3 pieces: $2 + 2 + 3 \implies p[2] + p[2] + p[3] = 5 + 5 + 8 = 18$ .

No other partition achieves 18. Hence, $R_7$ is achieved by exactly three different solutions (Statement C is correct). Because solution $(2, 2, 3)$ consists of three pieces, Statement D is false.

Therefore, statements A and C are correct.

Final answer

A, C

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2021 Computer Science and Information Technology (CS, Set-1)
Question: 50 of 65, printed as CS Q.40
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source