Answer the questions below. You will be asked to present your work after the breakout so make sure to indicate your answers clearly and concisely.
Consider a modification of the rod-cutting problem in which, in addition to a price pi for each rod, each cut incurs a fixed cost of c. The revenue associated with a solution is now the sum of the prices of the pieces minus the costs of making the cuts. (Adapted from Cormen et al. page 370)
Paste your dynamic programmic algorithm for the original rod-ccutting problem and make the necessary adjustments for the rod-cutting problem with cost.
Use the new set of prices which are as follows:
defextended_bottom_up_cut_rod(p,n,c):""" Implements a bottom-up dynamic programming approach to the rod cutting problem. Here, "extended" means the function is geared in a way amenable to reconstructing an optimal solution, on top of the returned optimal value. See Cormen et al., p. 369 for the implementation details. Inputs: - p: list of floats, the prices of rods of different lengths. p[i] gives the dollars of revenue the company earns selling a rod of length i+1. - n: int, length of the rod - c: constant cost per each cut Outputs: - r: list of floats, the maximum revenues. r[i] gives the maximum revenue for a rod of length i. As such: * r = 0 * len(r) == n + 1 - s: list of ints, the optimal sizes of the first piece to cut off. Also make sure that: * s = 0 * len(s) == n + 1 """#initialize the listsr=*(n+1)s=*(n+1)#for each nforjinrange(1,n+1):#note that we would need to get an even more negative number for different inputsq=float(-100000)#for each sublengthforiinrange(1,j+1):ifq<p[i-1]+r[j-i]-s[j]*c:q=p[i-1]+r[j-i]-s[j]*cs[j]=ir[j]=qreturnr,sp=[2,8,8,9,10,17,17,20,24,30]c=2n=10extended_bottom_up_cut_rod(p,n,c)
defprint_cut_rod_solution(p,n):""" Gives a solution to the rod cutting problem of size n. Inputs: - p: list of floats, the prices of rods of different lengths. p[i] gives the revenue (in USD, for example) the company earns selling a rod of length i+1. - n: int, length of the rod Outputs: - sol: a list of ints, indicating how to cut the rod. Cutting the rod with the lengths given in sol gives the optimal revenue. * print_cut_rod_solution(p,0) ==  """r,s=extended_bottom_up_cut_rod(p,n)whilen>0:print(s[n])#printing the optimal cut sizesn=n-s[n]
Find the cost for which 2 cuts of 10 is again an optimal solution when the rod is of length 20.