动态规划--改进的自下而上切割算法

Question

我对如何修改自下而上的切割杆算法以包含每次切割的固定成本c感到有点困惑。使收益等于零件价格减去成本的和。我有类似的东西，但我不确定我是否在正确的轨道上。

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]

Answer 1

您需要修改以包括不会进行削减的用例，其中不会产生固定成本"c“。

修改

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

解释

第4行:在这里，初始化为-inf将错过总成本不包括固定成本的用例。

第5行:i等于j的情况包含在第4行的初始化中。

来源：http://ranger.uta.edu/~huang/teaching/CSE5311/HW3_Solution.pdf