Consider a modification of the rodcutting problem in which i

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. Give a dynamic-programming algorithm to solve this modified problem.

Solution

MODIFIEDCUTROD (p, n, c)

r [ 0 . . n ] new array

                 r [ 0 ] = 0

               for j = 1 to n

                q = p [j]

              for i= 1 to j 1

            q = max (q, p [i] + r [ji] c)

          r [ j ] = q

return r [ n ]

Modification needed in the body of the inner for loop and reads q = max (q, p[i] + r [j i] c). This change may affect the fixed cost of making the cut and it is deducted from the revenue. The total revenue in this case is basically p[j]. And change the inner for loop to run from i to j – 1 instead of to j.