# Python program to solve the “rod-cutting problem”

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.