GATE CSE 2021 | Set 1 | Question: 40

Question

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

• A. $R_7=18$
• B. $R_7=19$
• C. $R_7$ is achieved by three different solutions
• D. $R_7$ cannot be achieved by a solution consisting of three pieces

Comments

It is a DP problem of cutting a rod.

---

any logic behind selling 2 meters rod two times ???

---

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n = 7;
    int price[] = {0,1,5,8,9,10,17,18};
    int dp[8] = {0};

    for(int i = 1; i <= n; i++) 
    {
        int best = 0;
        
        for(int j = 1; j <= i; j++) 
            best = max(best, price[j] + dp[i - j]);
        
        dp[i] = best;
    }

    cout << dp[n] << endl;
    return 0;
}

 

Answer 1

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$

Comments

Why we can't achieve 19 ???p(1)+p(7)

---

because question is asking about rod of length 7 meters (R7)....if we take 1 & 7 it will become 8

---

p1+p7 = 8 but we can need only the sum R7

Answer 2

Answer is (A) & (C)
This question is similar to 0/1 Knapsack.

1. Include 7 length rod  => Profit of 18.

Now, traverse through the path where we don't include 7.

2. Include 6.

   Only 1 case (6,1) again leads to a profit of 18.

Now, traverse through the path where we don't include 6.

3. Include 5.

   Two cases: (5,2) => Profit 15 and (5,1,1) => Profit 12

4. Dont include 5, Include 4.
   Three Cases:
      (4,3) => 17
      (4,2,1) => 15
      (4,1,1,1) => 12

5. Dont include 4, Include 3
      (3,2,2) => 18
      (3,2,1,1) => 15
      (3,1,1,1,1) => 12

6. Dont include 3, Include 2
     (2,2,2,1) => 16
     (2,2,1,1,1) => 13
     (2,1,1,1,1,1) => 10

7. All 1s => 7

Answer 3

ANSWER : A,C

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 . 

Comments

Yup cool 👍

---

Is it allowed to take two times P[2]??

---

Yes we can use any rods multiple times until unless it violates the optimal conditions @SUTAMA

Answer 4

It is not difficult to see that the optimal solution for the rod cutting problem is determined by the recurrence:

$R(n) = max_{0<=i<= n} (R(n-i) + p[i])$.

$R(0) = 0$

We can see that a bottom-up dynamic programming approach will be easier here, starting from n = 1. The table is filled below, step-by-step.

$R(1) = max(R(0) + p[1]) = 1$

$R(2) = max(R(0) + p[2], \ R(1) + p[1]) = max(5, 1+1) = 5$.

$R(3) = max(R(0) + p[3], R(1) + p[2], R(2) + p[1]) = max(8, 1+5, 5 + 1) = 8$.

 

 

	n = 1	n = 2	n = 3	n = 4	n = 5	n = 6	n = 7
R(n)	1	5	8

 

 

$R(4) = max(R(0) + p[4], R(1) + p[3], R(2) + p[2], R(3) + p[1]) = max(9, 1+8, 5 + 5, 8+1) = 10$

 

	n = 1	n = 2	n = 3	n = 4	n = 5	n = 6	n = 7
R(n)	1	5	8	10

 

 

$R(5) = max(R(0)+p[5], R(1) + p[4], R(2) + p[3], R(3) + p[2], R(4) + p[1]) = max (10, 1+9, 5+8, 8+5, 10+1) = 13$.

 

	n = 1	n = 2	n = 3	n = 4	n = 5	n = 6	n = 7
R(n)	1	5	8	10	13

 

$R(6) = max(R(0) + p[6], R(1) + p[5], R(2) + p[4], R(3) + p[3], R(4) + p[2], R(5) + p[1]) = max(17, 1+10, 5+9, 8+8, 10+5, 13 + 1) = 17$ 

 

	n = 1	n = 2	n = 3	n = 4	n = 5	n = 6	n = 7
R(n)	1	5	8	10	13	17

 

 

$R(7) = max(R(0) + p[7], R(1) + p[6], R(2) + p[5], R(3) + p[4], R(4) + p[3], R(5) + p[2], R(6) + p[1])=$

$ max(18, 1+17, 5+10, 8+8, 13+5, 17+1) = $

$ max(18, 18, 15, 16, 18, 18)$.

 

Thus $R(7) = 18$. 

We see that $R(7)$ is obtained by four different values of 18. Option D cannot be correct as split (2, 3, 2) produces an optimal solution, which can be identified using the calculations above.

 

Therefore, only options A and C are correct.

 

 

Answer 5

😁 Its the easiest question I have seen in a long time 

Ans : A and C 

18 is the maximum you can get in profit by taking (7) OR (6,1) OR (2,3,2)= 18

as you can see these are 3 Different solutions shown above hence satisfies 2 given options  

Comments

Bro why can't we achieve 19 p1+p7??

---

length of rod is 7 .if we take p1 and p7 than length will be 8.

---

🖕