Exercise 15.1.3

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 $c$. The revenue associated with a solution is now the sum of the prices of the pieces minus the costs of making the cuts. Give a dynamic-programming algorithm to solve this modified problem.

The algorithm is pretty straightforward, and outlined below – you subtract $c$ from the calculation whenever there is a cut to be made.

But more importantly, it reduces to the original problem – if we subtract $c$ from each $p_i$ and then add $c$ back to the result, we get the same value and the same cuts.

Python code

def cut_rod(length, prices, cut_cost=0):
    values = [-1] * (length + 1)
    choices = [-1] * (length + 1)
    values[0] = 0

    for j in range(1, length + 1):
        max_cut = min(len(prices), j + 1)
        max_value = -1
        for i in range(1, max_cut):
            value = prices[i] + values[j - i] - (0 if j - i == 0 else cut_cost)
            if max_value < value:
                max_value = value
                choices[j] = i

        values[j] = max_value

    n = length
    cuts = []
    while n > 0:
        cuts.append(choices[n])
        n -= choices[n]

    return (values[length], cuts)