3,313 views

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

It is a DP problem of cutting a rod.
any logic behind selling 2 meters rod two times ???

Subscribe to GO Classes for GATE CSE 2022

A & C should be correct

• $1^{st}$ Solution $: p[2];p[3];p[2] = 5+8+5 = 18$
• $2^{nd}$ Solution $: p[7] = 18$
• $3^{rd}$ Solution $: p[6]; p[1] = 17+1 = 18$
by
2 3 12

one doubt cutting a rod into one or more pieces .How can we cut a rod into 1 piece isn’t the wordings ambiguous
They have given rod of n length out of which if we cut 7 meter rod then that will give us 1 piece rod of 7 meter, and other part will be of n-7 meter length which we will not consider as R7 is asked in question.

Correct me if i am wrong :)

R7 is the maximum profit obtained such that the rod is cut in one or more pieces , if we take the whole rod as of length 7 and not divide it it will still be 1 piece. Hence, it will be considered as a valid option. Both A and C are correct.

cutting a rod into 1 piece ? doesn’t sound ambiguous
In question it says that Rn is achieved by selling the peices how P[2] can be sell two times in solution to obtain R7 as 18

1st : directly from p[7]= 18

2nd  : p[6] + p[1]= 18

3rd : p[2] + p[3] + p[2]= 5+8+5= 18

and these are the only 3 ways you can try other combinations but these only are gives maximum .