Problem 55290. Cut the rod

Asif Newaz

12 solvers

3 likes

Solve

Solve Later

A rod of length n can be cut in different sizes. Different price is associated with different length of cuts. 
length, len= [1, 2, 3, 4, 5,  6,   7,  8]
price, p     = [1, 5, 8, 9,10,17,17,20]
Here, if you cut a piece of length 5, the price for that piece is 10. For length of 8, the price is 20.
Say, you have to obtain a rod of length x. By cutting the rod in which way will give you the maximum price.
For instance, say x=4. you can cut the rod in pieces like (1,3)/(3,1), (2,2), (1,1,1,1), (1,1,2)/(1,2,1)/... or (4).
The maximum revenue that you can get here is when you cut the rod in (2,2) pieces to get length x => 5+5=10. 
For (1,3)=>9; (1,1,1,1)=> 4; (1,1,2)=>7, (4)=>9. 
In this problem, you have to return the maximum reveneue you can obtain by cutting the rod of size x.