Dynamic Programming - Modify bottom-up rod cutting algorithm

1
votes

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]
1
algorithmdynamic-programmingbottom-up
Please be more specific about the optimization problem to be solved; do you mean the following problem? faculty.ycp.edu/~dbabcock/cs360/lectures/lecture12.html – Codor
You are on Right track. Your also does, what you want it to do. – user3401643
your approach is correct – user4408702

1 Answers

0
votes

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