CODEWITHSUNDEEP
algorithmdynamic-programmingbottom-up
tom3322
tom3322

Reputation: 133

Dynamic Programming - Modify bottom-up rod cutting algorithm

I'm a little confused on how to modify the bottom-up-cut-rod algorithm to include a fixed cost c for each cut. Making the revenue the sum of the price of the pieces minus the cost. I have something like this but I'm not sure if I'm on the right track.

MODIFY-BOTTOM-UP-CUT-ROD(p,n)
1.  let r[0..n] be a new array
2.  r[0] = 0
3.  for j = 1 to n
4.     q = -INF
5.     for i = 1 to j
6.        q = max(q,p[i] + r[j-i] - c)
7.     r[j] = q
8.  return r[n]

Upvotes: 2

Views: 1667

Answers (1)

Chaipau
Chaipau

Reputation: 369

You need to modify to include the use case where no cuts would be made, wherein the fixed cost "c" won't be incurred.

Modifications

4. q = p[j]
5. for i = 1 to j-1

Explanations

Line 4: Here, initializing to -inf would miss the use case where the total cost excludes the fixed cost.

Line 5: The case where i is equal to j is included in the initialization on line 4.

Source : http://ranger.uta.edu/~huang/teaching/CSE5311/HW3_Solution.pdf

Upvotes: 1

Related Questions