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

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. 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.

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]

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.

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__.

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

**Related Posts:**

- Practice Programming MCQs
- Apply for Python Internship
- Check Information Technology Books
- Apply for Programming Internship
- Check Python Books