in Algorithms retagged by
8,122 views
15 votes
15 votes

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
in Algorithms retagged by
by
8.1k views

2 Comments

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

3 Answers

25 votes
25 votes

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$

4 Comments

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
0
0

@debmalyaSEN Cutting a Rod into 1 piece = keeping the rod as a whole single piece. Hence it’s valid.

@unnayansharma p[2] just says the price of a piece of length 2. Imagine the rod is cut into 3 pieces of lengths : (2 units, 3 units, 2 units)

0
0
0
0
1 vote
1 vote

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 . 

3 Comments

P1+P3+P4 ALSO MAKING 18 RIGHT???
0
0

@Priyotosh2001 No because 1+3+4 != 7 , we wanted a rod of length 7 only

1
1
Yup cool πŸ‘
0
0
0 votes
0 votes

😁 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 (5,2) OR (2,3,2)= 18

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

Answer:

Related questions