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.

1

Consider a modification of the rod-cutting problem in which, in addition to a price $p_i$ 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)

2

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 |

3

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)

4

([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]

5

Question 2

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

6

In [ ]:

## your code here

7