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)
No comments:
Post a Comment