CoCalc Public Files11.1 | Rod-cutting with costs | Group 1.ipynb
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 : 63

### BREAKOUT INSTRUCTIONS

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)

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