11.1 | Rod-cutting with costs | Group 1.ipynb

Kernel: Python 3 (system-wide)

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 $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

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])

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.

## your code here