Find price for Rod cutting

Question

Given Length of Rod and P (Price ) for the first 3 rods. We are to fill in the possible price we can get for the rest of rods. Assuming we can cut the longer pieces as needed.

L = 1     2       3      4       5        6         7          8 
p = 3     8       12 

We basically want to get the maximum price we can get for each missing length price.

My approach I believe that since we are given the best possible price for a rod of length 1,2, and 3 we can generate all possible combinations for the next rods.

For example to get price of rod where L = 4 
price of rod where L = 1 + rod where L =  3 = 15
price of rod where L =  2 + rode where L =  2 = 16
Therefore price of rod wehre L = 4  = 16 since 16 > 15.

For example to get price of rod where L = 5
price of rod where L = 1 + rod where L = 2 and rod where L = 2 = 19
price of rod where L = 3 + rod where L = 2  = 20
price of rod where L = 4 + rod where L = 1 = 19

So this is kind of the approach i am following. However I am not sure if i am correct. I would also like it if someone can verify this approach and also maybe help me derive a formula from this. I am not looking for code as understanding the problem is enough to write the code.

Answer 1

You can check the explanation of a variation of this problem in CLRS (section 15.1, page 360). The problem is called the Rod Cutting problem.

Your approach is correct, and you can formalize it as a recurrence relation.

f(n) = min(f(n - i) + price(i)).    1 <= i <= n - 1

where f(n) is the minimum price to buy a rod of length n. using memoization, this can be calculated in O(n^2).

Answer 2

Your approach is correct. It can also be done in another way as answered by MrGreen (https://stackoverflow.com/a/29352580/13106102)

Let, B(i) = optimal price for cutting a rod of length i units and p(i) = price of a rod of length i units.

Formula 1: B(i) = max(1<=k<=floor(i/2)) {B(k) + B(i-k)} and P(i)

Formula 2: B(i) = max(1<=k<=i) {p(k) + B(i-k)})

Consider a rod of length 4, it can be cut in the following ways :

1) uncut of length 4

2) 3, 1

3) 2, 2

4) 2, 1, 1

5) 1, 3

6) 1, 2, 1

7) 1, 1, 2

8) 1, 1, 1, 1

According to Formula 1:

option 1 corresponds to P(4)

option 2,5,6,7,8 corresponds to B(1) + B(3)

option 3,4,6,7,8 corresponds to B(2) + B(2)

According to Formula 2:

option 1 corresponds to P(4)

option 2 corresponds to P(3) + B(1)

option 3,4 corresponds to P(2) + B(2)

option 5,6,7,8 corresponds to P(1) + B(3)

So to conclude, 1 and 2 are counting the optimal solution but in different ways, where 2 is more compact and makes lesser recursive calls compared to 1.