Shared11.1 | Rod-cutting with costs | Group 1.ipynbOpen in CoCalc
Authors: Recording Agent, Zainab Ahmed, Gadi Borovich, Yuanhui Cai, César Castro, Anh Chu, Leroy Anthony Drummond, Johannes Maria Halkenhaeusser, Jasen Lo, Rebecca Mqamelo, and 3 more authors...
Views : 16

BREAKOUT INSTRUCTIONS

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 pip_i for each rod, each cut incurs a fixed cost of cc. 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)

Question 1

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:

Length 1 2 3 4 5 6 7 8 9 10
Price 2 8 8 9 10 17 17 20 24 30
In [7]:
def extended_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] = 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] = 0 * len(s) == n + 1 """ #initialize the lists r = [0]*(n+1) s = [0]*(n+1) #for each n for j in range(1, n+1): #note that we would need to get an even more negative number for different inputs q = float(-100000) #for each sublength for i in range(1, j +1): if q < p[i - 1] + r[j - i] - s[j]*c: q = p[i - 1] + r[j - i] - s[j]*c s[j] = i r[j] = q return r, s p = [2,8,8,9,10,17,17,20,24,30] c = 2 n = 10 extended_bottom_up_cut_rod(p,n,c)
([0, 2, 6, 8, 12, 14, 18, 20, 24, 26, 30], [0, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2])
In [ ]:
def print_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) while n > 0: print(s[n]) #printing the optimal cut sizes n = n - s[n]

Question 2

Find the cost for which 2 cuts of 10 is again an optimal solution when the rod is of length 20.

In [ ]:
## your code here