GATE CSE 2021 Set 1 Q50: Rod cutting: maximum revenue for a rod of length 7

Algorithms
2 marks
MSQ
No negative marking

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

Try it: multiple select: one or more correct options

Select all correct options. No negative marking, no partial marks.

Show answer and explanation

Answer: A, C (official GATE 2021 final answer key)

Concept used: Rod cutting by dynamic programming: $R_n = \max_{1 \le i \le n} (p[i] + R_{n-i})$ .

First step: Build $R_1, R_2, \dots$ in order: $R_1 = 1$ , $R_2 = 5$ , $R_3 = 8$ , $R_4 = 10$ , and continue to $R_7$ , noting every split that attains the maximum.

Full step-by-step solution

Detailed working, common mistakes and linked mock tests will be available with a free GATEiit account. Log-in is coming soon.

Share this question

WhatsAppDownload image

Source: official GATE 2021 Set 1 CS question paper and final answer key, organised by IIT Bombay. Question paper · Answer key

PracticePractise Algorithms questions →Full paperAll GATE CSE 2021 Set 1 questions →

GATE CSE 2021 Set 1 Q50: Rod cutting: maximum revenue for a rod of length 7

Question

Full step-by-step solution

More Algorithms PYQs