Rod Cutting Problem

Problem statement

You are given a rod of size n > 1, it can be cut into any number of pieces k. The price for each piece of size i is represented as price(i) and the maximum revenue from a rod of size i is r(i) (could be split into multiple pieces). Find r(n) for the rod of size n.

Consider that the length of the rod is 6. The price of size is given below:

Length	1	2	3	4	5	6
Price(p)	2	5	8	9	10	11

The possible number of rods after cutting can give the following price:

Rod(6)	1*6	1*4, 2	1*3, 3	1, 2, 3	1*2, 4	1, 5	2*3	2, 4	3, 3
Price(p)	12	13	14	15	13	12	15	13	16

So the maximum revenue is 16 for the rod that can be cut in (3,3), i.e., 2 pieces.

Solution: Recursive Approach

Here we have to generate all the configurations of different pieces and find the highest priced configuration. We can get the best price (maximum revenue) by making a cut at different positions and comparing the values obtained after a cut.

If RodCut(n) is the function that gives the value of r(n), then RodCut(n) = max(p(i) + RodCut(i)).

Let’s move to the implementation now. In this lesson, we will build a solution using the recursive approach, and then in the next lesson, we will implement a more optimized approach to solve this problem.