What is rod cutting problem?

A rod of length n is given with the price of each piece of rod with length less than n. The problem is to find the maximum profit that can be obtained by cutting the rod into pieces. Consider, every piece of rod with different length

$i_s$, has different rates $i_r$ associated with it.  To get the maximum revenue r out of it, r can be defined as

$r = \sum _{}^{} \left(i_r \times i_s\right)$

For example, consider a rod of length 3. The pieces with length 1 and 2 has the rate 3 and 5 respectively. Then the maximum profit is obtained by cutting the rod into three pieces with length 1 (3+3+3=9), which is 1 more than cutting it into two pieces(3+5=8).

Types of Solutions

• Naive Solution- Naive method tells to generate all configurations of pieces and then find the maximum-priced configuration.
• Optimal Substructure- This method uses the approach of cutting the rod at different positions and then compare the values after cutting. Then call the function recursively for the piece obtained after the cut.
• Bottom-Up Approach- In this approach, the smaller sub-problems are solved first. Then, the larger sub-problems are solved using the result of smaller problems.
• Dynamic Programming approach - Dynamic programming works in a bottom-up manner. First, solve all smaller sub-problems and then build solution for larger problems.

Naive solution

A naïve solution for the above-stated problem is to evaluate all of the possible combinations of different pieces of varying size to find the maximum revenue-generating combination. Although this method seems the easiest and quick to practice, it has exponential time complexity. So there is a need to figure out a better method than this.

Optimal substructure

The basic idea is to divide the rod of length n, into two parts i and n-i. Repeat the process for the rod of length n-i but do not consider the rod of length n anymore, because it is already divided. Finally, take the maximum of all values. This yields the following recursive relation:

R_cut(n) = max { price[i – 1] + R_cut(n – i) } where 1 <= i <=n

Array price stores the rate of the rod of length i in price[i-1]. The time complexity of this approach is O(nⁿ) , because each problem with size n is divided into n-1 subproblems. Consider a recursion tree for the rod of length 4.

Each problem is divided into sub-problems, which will be recursively divided into its sub-problems, till they cannot be divided further. So, the problem has an optimal substructure. By selling the smaller pieces at a higher price, maximum profit is obtained. This property is called optimal substructure.

In the recursion tree, the same subproblems (highlighted in the same color) are getting computed repeatedly. So, the problem also exhibits overlapping subproblems. In dynamic programming, the subproblem solutions will be memoized to avoid computing the same thing again.

Bottom-up approach

In the bottom-up approach, the smaller subproblems are solved first, then solve larger sub-problems from them. The maximum profit for a smaller length rod will be memoized and these maximum values will be used in computing it for long rods.

In this approach, an array is maintained to store the maximum profit that can be generated by a piece of rod with length i, where i is less than n. So starting from storing maximum profit smaller pieces, the maximum profit of longer rod can be obtained. The pseudocode for the approach is given below:

$$\begin{gathered} 1. Initialize an array B[0...n] \\ 2. B\left[0\right]=0 \\ 3. for b=1 to n \\ 4. s=-\infty \\ 5. for a= 1 to b \\ 6. s=max\left(s,price\left[a\right]+B[b-1]\right) \\ 7. B\left[b\right]=s \\ 8. return B\left[n\right] \end{gathered}$$

The bottom-up approach stores the maximum profit that can be obtained from a rod of length i in array B[i]. It is the maximum of rate obtained by keeping the rod as it is or dividing it as a combination of smaller lengths. As the approach uses two for loops only, the time complexity of this approach is O(n²).

Dynamic programming approach

Rod cutting is a problem that can be solved with many other approaches but can be optimized greatly by using a dynamic programming approach. Since dynamic programming is mainly an optimization-over-plain recursion, it can be used to optimize the exponential time algorithm. The idea is to save the solutions of sub-problems so that no need to re-compute them when they are needed. Dynamic programming (DP) and Divide and Conquer (D&C) follow the method of partitioning a complex problem into smaller easier subproblems, finding the solutions to this smaller problem which eventually gives a solution to the larger problem. But in Divide and Conquer the overlapping of sub-problems is not considered, and there is higher computation overhead. In DP, the large subproblems reuse solutions of the smaller problem, which is already computed.

Two main approach of DP are there: top-down and bottom-up. In top-down approach, it will start to solve problem by dividing it. The result of solved sub-problems are used when it occurred again. Main idea of bottom-up approach is- don’t wait until all subproblem is generated. In this approach, the subproblems are sorted on size, so that smaller subproblems are solved first and they are combined to solve larger ones. Both algorithms have the same asymptotic cost: $O\left(n^2\right)$, but bottom-up is usually faster.

For a rod of length n, a cut be made at 1 unit of length, there will be two pieces. Now the goal is to generate maximum revenue from these two pieces only. That is, to sell these pieces optimally. Therefore, the first piece will be sold at a rate of $r_1$ and the second at $r_{n-1}$. Similarly, if a cut is made at length 2 units, then the rate of pieces are $r_2$ and $r_{n-2}$ and so on. The Dynamic Equation will be:-

$r_n=max\left\{price\left[n\right],\left(r_1+r_{n-1}\right),\left(r_2+r_{n-2}\right),\dots ,\left(r_{n-1}+r_1\right)\right\}$

The time complexity of this approach is $O\left(n^2\right)$.

Common Mistakes

Rod cutting problem can be solved using different approaches. People may think, Naive approach is better, as the solution will be easily obtained for smaller length rod. But in case of larger length rod, or when the size is not known, the complexity of this approach is high. In Optimal substructure approach, the problem is divided in to subproblem and these subproblems are further divided which makes it easier to solve a larger problem. One thing to note here is that if the same problem n is considered for division rather than n-i, it will enter in an infinite loop.

Related Concepts

• Recursive Approach
• Top Down Approach
• Dynamic Programming
• Bottom-up Approach

Context and Applications

This topic is significant in the professional exams for both graduate and postgraduate courses, especially for:

• Bachelor of Technology
• Master of Technology
• Bachelor of Engineering
• Master of Engineering

Practice Problems

Q1. Dynamic Programming is used in rod cutting for:

a) Optimized solution

b) Faster calculation

c) Optimal Substructure

d) Getting subproblem

Correct Ans- a) Optimized Solution.

Explanation: The fastness of the solution depends on the input size also. For some input sizes, some other algorithms/approaches also can be better. However, the dynamic programming method is used for an optimal solution for a large input size.

Q2. A method that cuts the rod in all possible ways in a rod cutting problem is

a) Optimized solution

b) Dynamic programming

c) Naive Method

d)Top-down approach

Correct Ans- c) Naive Method

Explanation: Obtaining maximum profit by considering all possible solutions is the Naive approach. All other methods, solve the problem by some specific steps.

Q3. Time complexity of dynamic programming in rod cutting is
a)$O\left(n^2\right)$ 

b)$O\left(\mathrm{logn}\right)$

c) $O\left(n\right)$

d) None of these

Correct Ans- (a)$O\left(n^2\right)$

Explanation: The dynamic programming approach divides the problems into subproblems and solves them independently to find the optimal solution. So, the time complexity relates to the square of the input size.

Q4. Time complexity of Naive approach of solving rod cutting is
a) $O\left(n^2\right)$

b)$O\left(2^n\right)$

c)$O\left(\log n\right)$

d)$O\left(n\right)$

Correct Ans- (b)$O\left(2^n\right)$

Explanation: The Naive approach considers all the possible combinations of rate and length. So, the complexity is exponential.

Q5. Consider the following data:

What is the maximum profit that can be obtained for a rod of length 6?

a) 12

b) 15

c) 12

d) 13

Correct answer: b) 15

Explanation: The maximum profit can be obtained by the length combination {2,2,2}=5+5+5=15