CLRS Exercise 15.1-3 Rod Cutting Problem with cost

My Macroeconomics class starts to talk about dynamic optimization this week, so I think it might be a good idea for me to jump ahead to work on some dynamic programming problems in CLRS books. Knowing how to formulate a problem in a recursive manner is the key in this type of problems, but for programming (here I mean computer programming), it takes more thinking. In this case, the rod cutting problem is easy to formulate: \begin{equation*} \begin{aligned} & r(n,c) = \underset{I}{\text{maximize}} & & \sum\limits_{i \in I} p_i + r(n-i,c) - |I| * c\\ & \text{subject to} & & \sum\limits_{i \in I} i = n. \end{aligned} \end{equation*} That is we want to find a set \( I\) such that the objective function is maximized. In dynamic programming terminology, \( r(n,c)\) is called the value function, and \(n,c\) are the state variables. Our control variable is the set \(I\). What follows is the code that solves this problem. Things to notice.

• r and s have size n+1. These two arrays solve problems of size 1 up to n, the solution when size =0 is trivially set to 0.
• s[i+1] = j+1. This feels odd, but it is to conform to the interpretation of the point above. So s[i] gives us the cut that we need when the problem size is i.

import numpy as np
def rod_cutting_with_cost(p, n,c):
    r = [0 for i in range(n+1)]
    s = [0 for i in range(n+1)]
    
    for i in range(n):
        q = -np.inf
        for j in range(i+1):
            if j == i:
                if q < p[j] + r[i-j]:
                    q = p[j] + r[i-j]
                    s[i+1] = j+1
            else:
                if q < p[j] + r[i-j] - c:
                    q = p[j] + r[i-j] - c
                    s[i+1] = j+1
        r[i+1] = q
    return r,s

def print_cuts(s,n):
    i = n
    print i-s[i]
    i = s[i]
    while s[i] != i:
        print i-s[i]
        i = s[i]

p = [1,5, 8, 9, 10, 17,17,20,24,30]
print rod_cutting_with_cost(p,10,0)
print rod_cutting_with_cost(p,10,1)
print rod_cutting_with_cost(p,10,2)
print rod_cutting_with_cost(p,10,3)