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