Solving The Rod Cutting Problem

Recursive Approach vs. Dynamic Programming

Hope you all doing well.

In this article, I’m going to talk about the following things.

∘ Recursion
∘ Dynamic Programming
∘ Rod-Cutting Problem
∘ Rod-Cutting Problem — Recursive Approach
∘ Rod-Cutting Problem — Dynamic Programming Approach

Recursion

Photo by Fabrice Villard on Unsplash

In computer science, recursion is a technique to solve problems whose solutions depend on the smaller instance of the same problem. It defines the problem in terms of itself. It is one of the most powerful tools in writing algorithms. It comes directly from Mathematics as there are many expressions with respect to the problems themselves.

For example, in Fibonacci Sequence generation, we use F(i)=F(i-1)+F(i-2) and it is a recursive operation. Okay, no worries. Read further if you’re not convinced.

Look at this example

The ultimate goal is to reach home. Therefore the problem is, ‘How to go home?’. There are two possible moves we can do.

1. Stop moving (if the person is at his home).
2. Make a step towards home (if the person is not at his home).

Here, the same problem ‘How to go home?’ will be called recursively until we reach the house.

Now it makes some sense, right?

Recursive algorithms must have the following parts

1. Base Case (Termination point)
2. Work toward Base Case
3. Recursive Call (Calls the same defined function)

In a recursive algorithm, the computer remembers every previous state of the problem. This information is held by the computer on the activation stack (inside of each function’s workspace). And every function has its own workspace PER CALL of the function.

Some recursive algorithms are comparable to loops. Such algorithms are called tail-recursive because the last statement in the algorithm is to reset the algorithm. Tail recursive algorithms can also be translated directly into loops.

Image by Author

This is the recursion tree for finding nth Fibonacci Element (n=6); here you can see the repetition of similar sub-problems and this makes the problem’s Time Complexity go exponential.

Dynamic Programming

Dynamic programming is a method used to solve recursive problems with a heavily overlapping sub-problem structure. Heavily overlapping refers to the recurring sub-problems again and again.

Image by Author

In performance analysis, we consider Space and Time complexities. Here in Dynamic Programming, we trade space for time.

Photo by Jon Tyson on Unsplash

But how to do trade-off in between Time and Space? Well, that is why we are using Dynamic Programming!

In Dynamic Programming, it solves each sub-problem only once and then saves its solution in a table, avoiding the tasks of re-computing the answer every time it solves each sub-problem. So we increase the Space and in the meantime, we reduce the time consumption for the execution by avoiding the repetition of the same sub-problems.

Image by Author

In Dynamic Programming, the nodes in red won’t be executed as it happened in the recursive approach as the same nodes have already been computed and the values are already stored in the respective positions that are going to be used again if needed.

Now, let’s go into our problem, Rod-Cutting! There is another problem similar to this called the Cutting stock problem.

Rod-Cutting Problem

There is a rod of length n (whatever the unit; say meters) and there is a price list of rod length i meters where 1 ≤ i ≤ n. We have to find the optimal way of cutting the rod we have (length of n meters) to maximize the profit.

Length (i meters) 1   2   3   4    5    6    7    8    9   10
Price (pᵢ)        1   5   8   9   10   17   17   20   24   30

For example, let’s see the explanation for the solution first.

The rod length available is 4 m. First, let’s see how we can cut it. How many possibilities are there to cut this rod? 2ⁿ/2 different ways.

That is; if n = 4, ²⁴/2 = 16/2 = 8 different ways.

Image by Author

Cut                                         Profit
4                                             9
2, 2                                  5 + 5         = 10
1, 3                                  1 + 8         = 9
3, 1                                  8 + 1         = 9
1, 1, 2                               1 + 1 + 5     = 7
1, 2, 1                               1 + 5 + 1     = 7
2, 1, 1                               5 + 1 + 1     = 7
1, 1, 1, 1                            1 + 1 + 1 + 1 = 4

So the best cut is a 2, 2 pattern in which we can get the maximum profit of 10.

How this problem comes into the recursive approach and how can it be solved by Dynamic Programming?

Let’s first see how this can be solved in a recursive approach.

Rod-Cutting Problem — Recursive Approach

We are given an array price[], where the rod of length i has a value of price[i-1]. The idea is simple; one by one, partition the given rod of length n into two parts; i and n-i. Now we have n-i as rod length and have to recur again till it reaches a point where we have 0 as the rod length. Then we have to take max among the computed price. So the recursive function would be

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

Image by Author

This can be implemented in C++ as this.

This can be implemented in Java as this.

The output when n=4 is

Profit is 10

What about the Time Complexity?

O(nⁿ); where n is the rod size.

Let’s solve this problem by using Dynamic Programming. But how we can say that this program can be resolved by Dynamic Programming?

Rod-Cutting Problem — Dynamic Programming Approach

Image by Author

As we can see, the same substructure (highlighted in the same color, red and blue) is getting computed repeatedly. So the problem exhibits overlapping subproblems. We know that problems with optimal substructure and overlapping subproblems can be solved by Dynamic Programming, where subproblem solutions are memoized rather than computing again.

Let’s solve this problem in a bottom-up approach. In the bottom-up approach, we solve similar subproblems first, and then we solve the larger sub-problems from them. The following approach computes T[i], which stores maximum profit obtained from the rod of length i for each 1≤i≤n, and then it uses the values of smaller values i which are already computed.

Cut                                         Profit
4                                             9
2, 2                                  5 + 5         = 10
1, 3                                  1 + 8         = 9
3, 1                                  8 + 1         = 9
1, 1, 2                               1 + 1 + 5     = 7
1, 2, 1                               1 + 5 + 1     = 7
2, 1, 1                               5 + 1 + 1     = 7
1, 1, 1, 1                            1 + 1 + 1 + 1 = 4

Let’s see how to implement this in C++.

This can be implemented in Java as this.

The output when n=4 is

Profit is 10

What about the Time Complexity?

This bottom-up approach costs O(n²) and required O(n) extra space; where n is the rod size.

You can figure out that we have made a trade-off between Time and Space.

Try to solve this using the Top-down approach.

Last point to note: Not every optimization problem can be solved in this manner, but it offers a good starting point.

Hope this helps. Share your thoughts too.