Question

Consider a modification of the rod-cutting problem in which, in addition to a price pi 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. Give a dynamic-programming algorithm to solve this modified problem. g

Answer 1

Answer:

Check the explanation

Explanation:

We muddy pseudo code for BOTTOM-UP-CUT-ROD by simply adding —c inside the parenthesis you have in line 6 (because that is were cut is made),

so that now it reads like this:

                                 $q=max(q,p[i]+r[j-i]-c)$

the after results will look like:

                           Modify pseudo code for BOTTOM-UP-CUT-ROD