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.

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.

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.

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]

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.

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.