1

我对如何修改自下而上的切割棒算法以包括每次切割的固定成本 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]
4

1 回答 1

0

您需要修改以包含不会进行削减的用例，其中不会产生固定成本“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

于 2019-02-03T08:06:06.800 回答