An assignment at school required me to write a program for this task:

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.

Here is my solution to this task (in Python):

`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] `

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

Here is an example output –

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

Times taken for each function –

`%timeit cut_rod(p, n) 7.65 µs ± 71.7 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each) %timeit cut_rod_helper(p ,n, r, s) 266 ns ± 3.97 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each) `

So, I would like to know whether I could make this program shorter and more efficient.

Any help would be highly appreciated.