如何解决最大数量限制的杆切割 p?r?o?b?l?e?m 允许削减多少？

Question

我知道如何使用动态规划解决杆切割问题。但是，当我们限制允许的最大切割次数时，动态规划无法给出正确的答案。即使我也无法想到该问题的递归解决方案。帮助。

问题是，
确定通过切割杆并出售碎片可获得的最大收入。
给定长度为 N 的杆，以及长度为 i 的杆的价格表 P(i)。您可以在给定的杆上进行不超过 K 次切割。

示例：
N=10
K=3
| p(1) = 1 | p(1) = 1 p(2) = 5 | p(2) = 5 p(3) = 8 | p(3) = 8 p(4) = 9 |p(5) = 10| p(6) = 22 | p(6) = 22 p(7) = 17 | p(7) = 17 p(8) = 20 | p(8) = 20 p(9) = 24 | p(9) = 24 p(10) = 30 | p(10) = 30 |

将棒材切割成长度为 6 和 4 的 2 段（总切割次数 = 1，小于 K = 3），可获得的最大收入为 31。

Answer 1

我们可以通过添加第二维（即迄今为止的切割次数）来扩展动态规划解决方案。

\n\n

D[n][k]n，使用精确切割的长度杆的最大收入k可以定义如下：

\n\n

D[n][k] = max(price[i] + D[n-i-1][k-1]) for all i in {1, 2, ..., n}\n

\n\n

由于我们最多 K希望削减，而不是完全削减，因此最大收入将是：

\n\n

maxRevenue(N) = max(D[N][k]) for all k in {1, 2, ..., k}\n

\n\n

这将是O(N\xc2\xb2K)，因为我们需要遍历所有问题k（与O(N\xc2\xb2)经典问题相比）。

\n\n\n\n

（Java）代码：

\n\n

D[n][k] = max(price[i] + D[n-i-1][k-1]) for all i in {1, 2, ..., n}\n

\n\n

现场演示。

\n