# Python Program to Solve Rod Cutting Problem using Dynamic Programming with Bottom-Up Approach

This is a Python program to solve the rod-cutting problem using dynamic programming with bottom-up approach.

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. The function cut_rod takes two arguments, the list of prices, p and the length of the rod, n.
2. cut_rod creates two lists r and s.
3. r[i] is the maximum revenue we can earn and s[i] is the length of the first piece to cut from a rod of length i.
4. The list s will be used to figure out how to cut the rod to get maximum revenue.
5. r[0] is initialized to 0.
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. As the maximum revenues are calculated they are stored in r and the initial cuts are stored in s.
8. The function 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 bottom-up approach. 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)
r[0] = 0

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

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

return r, s

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.
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: 3
Enter the price of a rod of length 1 in: 1
Enter the price of a rod of length 2 in: 2
Enter the price of a rod of length 3 in: 2
The maximum revenue that can be obtained: 3
The rod needs to be cut into length(s) of 1 1 1

Case 3:
Enter the length of the rod in inches: 4
Enter the price of a rod of length 1 in: 1
Enter the price of a rod of length 2 in: 3
Enter the price of a rod of length 3 in: 2
Enter the price of a rod of length 4 in: 5
The maximum revenue that can be obtained: 6
The rod needs to be cut into length(s) of 2 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]