# Python Program to Solve Rod Cutting Problem using Dynamic Programming with Memoization

This is a Python program to solve the rod-cutting problem using dynamic programming with top-down approach or memoization.

Problem Description

In the rod-cutting problem, we are given a rod of length n inches and a table of prices p[i] for i = 1, 2, …, n. Here p[i] is the price of a rod of length i inches. We have to find the optimal way of cutting the rod so that maximum revenue can be generated by selling the pieces.

Problem Solution

1. Two functions are defined, cut_rod and cut_rod_helper.
2. cut_rod_helper takes four arguments, three lists p, s and r; and a number n.
3. Here p[i] is the price, r[i] is the maximum revenue we can earn, s[i] is the length of the first piece to cut from a rod of length i and n is the length of the rod given to us.
4. The list s will be used to figure out how to cut the rod to get maximum revenue.
5. cut_rod_helper fills the lists r and s as it runs.
6. The function fills r by using the formula r[i] = p[j] + r[i – j] for j such that p[j] + r[i – j] is maximum.
7. The function is implemented recursively and as maximum revenues are calculated they are stored in r and the initial cuts are stored in s.
8. If a maximum revenue has been already calculated and stored in r, then it is immediately returned and not calculated again.
9. The function cut_rod takes two arguments, the list of prices, p and the length of the rod, n.
10. cut_rod creates two lists r and s and calls cut_rod_helper to fill these lists.
11. It returns r and s.

Program/Source Code

Here is the source code of a Python program to solve the rod-cutting problem using dynamic programming with memoization. The program output is shown below.

```def cut_rod(p, n):
"""Take a list p of prices and the rod length n and return lists r and s.
r[i] is the maximum revenue that you can get and s[i] is the length of the
first piece to cut from a rod of length i."""
# r[i] is the maximum revenue for rod length i
# r[i] = -1 means that r[i] has not been calculated yet
r = [-1]*(n + 1)

# s[i] is the length of the initial cut needed for rod length i
# s[0] is not needed
s = [-1]*(n + 1)

cut_rod_helper(p, n, r, s)

return r, s

def cut_rod_helper(p, n, r, s):
"""Take a list p of prices, the rod length n, a list r of maximum revenues
and a list s of initial cuts and return the maximum revenue that you can get
from a rod of length n.

Also, populate r and s based on which subproblems need to be solved.
"""
if r[n] >= 0:
return r[n]

if n == 0:
q = 0
else:
q = -1
for i in range(1, n + 1):
temp = p[i] + cut_rod_helper(p, n - i, r, s)
if q < temp:
q = temp
s[n] = i
r[n] = q

return q

n = int(input('Enter the length of the rod in inches: '))

# p[i] is the price of a rod of length i
# p[0] is not needed, so it is set to None
p = [None]
for i in range(1, n + 1):
price = input('Enter the price of a rod of length {} in: '.format(i))
p.append(int(price))

r, s = cut_rod(p, n)
print('The maximum revenue that can be obtained:', r[n])
print('The rod needs to be cut into length(s) of ', end='')
while n > 0:
print(s[n], end=' ')
n -= s[n]```
Program Explanation

1. The user is prompted to enter the length of the rod n.
2. The user is then asked to enter the price for each length of rod from 1 to n inches.
3. cut_rod is called and the lists r and s are returned.
4. r[n] is the maximum revenue that we can earn from a rod of length n.
5. The way to cut the rod is determined using s where s[i] tells you the length of the first piece to cut of from a rod of length i.
6. So s[n] gives us the length of the first piece, s[n – s[n]] gives us the length of the second piece and so on.

Runtime Test Cases
```Case 1:
Enter the length of the rod in inches: 5
Enter the price of a rod of length 1 in: 1
Enter the price of a rod of length 2 in: 5
Enter the price of a rod of length 3 in: 8
Enter the price of a rod of length 4 in: 9
Enter the price of a rod of length 5 in: 10
The maximum revenue that can be obtained: 13
The rod needs to be cut into length(s) of 2 3

Case 2:
Enter the length of the rod in inches: 1
Enter the price of a rod of length 1 in: 5
The maximum revenue that can be obtained: 5
The rod needs to be cut into length(s) of 1

Case 3:
Enter the length of the rod in inches: 3
Enter the price of a rod of length 1 in: 3
Enter the price of a rod of length 2 in: 7
Enter the price of a rod of length 3 in: 2
The maximum revenue that can be obtained: 10
The rod needs to be cut into length(s) of 1 2```

Sanfoundry Global Education & Learning Series – Python Programs.

To practice all Python programs, here is complete set of 150+ Python Problems and Solutions.

Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!

If you find any mistake above, kindly email to [email protected]