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

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