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