Problem: We are given a rod of length l and an array that contains the prices of different sizes less than l. Our task is to piece the rod in such a way that the revenue generated by selling them is maximum.

For example, consider following given problem:

Rod cutting problem

We could get a maximum revenue of 18 if we cut the rod into two pieces of length 6 and 1.

Revenue table of rod cut

We can solve this problem using recursion and further optimize it using dynamic programming.

Solution using Recursion (Naive Approach)

We can cut a rod of length l at position 1, 2, 3, …, l-1 (or no cut at all).

price of rod cut piece

In each case, we cut the rod and sum the prices of the pieces. We compare the total revenue of each case and get the one which gives the maximum profit.

i.e., max(price[l-i] +price[i]) for all i in {0, 1 … l-1}

Because every piece after the cut is a rod itself, we recursively repeat the same process to get the max possible revenue for each piece.

i.e., max(rod_cutting(l-i]) +price[i]) for all i in {0, 1 … l-1}

Here is the implementation of the recursive solution in Python, C++ and Java:

Python

C++

Java

Max Revenue: 18

The time complexity of the above solution is O(nn).

The reason for such high time complexity is that the recursive solution computes overlapping subproblems multiple times.

For instance, when computing the max price of length=7, the price of some of the preceding lengths is calculated multiple times.

recursive calls in rod cutting recursive solution

We can leverage dynamic programming to significantly reduce the computational task of the recursive solution.

Solution using Dynamic Programming (Efficient Approach)

The idea is to store the solution of subproblems into a memo table (array) so that we can reuse them without computing it again i.e., store the max price of each length into an array when they are calculated for the first time.

rod cutting problem recursive calls with DP

Here is the implementation of the solution of the rod cutting problem using Dynamic Programming:

Python

C++

Java

Output:

Max Revenue: 18

The time complexity of this solution is O(n2). Since we are using an extra array for memorization, the space complexity for the program is O(n).

In this tutorial, we learned to solve the rod cutting problem using the concept of dynamic programming in C++, Java, and Python.

Leave a Reply