具有最大切削量的动态规划棒料切削问题及实际解

Question

所以我正试图为rod cutting problem的修改版本编写代码。这一联系使我们对问题有了很好的直觉。但是，我想修改代码，使之不仅实际返回解决方案，也就是说，什么样的切割给出了最优的解决方案，而且还将切割的数量限制为最大值k

为了证明概念，我正在尝试创建一个算法来实现这一点。下面是到目前为止，我认为它成功地返回了实际的解，但是，我不知道如何将最大值限制为k

 let r[0..n] be a new array
 r[0] = 0
 for j = 1 to n
    q = -1
    for i = 1 to j
        for k = 0 to n-1
          q = Math.max(q[n][k], p[i] + q[n-i-1][k-1]);
    r[j] = q
 return r[n]

请不要在你的答案中提供实际的代码，我想自己实现，我只需要帮助调整我的算法，以给出正确的解决方案。在

更新1：我已经能够通过在数组中添加第二个维度来找到最多k个切割的最佳解决方案。这在上面的代码中显示。在

Answer 1

正如你所说的，你已经有了最佳的解决方案，这个答案只包括如何追溯精确的解决方案（在每一步所做的削减）。在

将候选切割存储为length=n和maximum cuts=k

为此，您只需要一个二维数组（比如，visit[n][k]）来存储获得q[n][k]最大解的切割。就伪代码和递归关系而言，如下所示。在

for each value of i:
  q[n][k] = q[n][k-1]
  visit[n][k] = -1
  if q[n][k] < p[i] + q[n-i-1][k-1]:
    q[n][k] = p[i] + q[n-i-1][k-1]
    visit[n][k] = i

说明

• 有可能我们没有一个最大化解决方案的削减。在本例中，我们初始化visit[n][k] = -1。在
• 每一次，我们都有一个候选者在length=i+1处切割长度为n的杆，也就是说，我们可以通过切割获得更好的价格，我们将相应的切割存储在另一个二维数组中。在

重建解决方案

使用这个二维数组（visit[n][k]）来回溯精确的剪切，可以使用以下伪代码（我故意避免使用代码，因为您提到过您不需要它）。在

^{pr2}$

说明

• 我们从k迭代到0。在
• 每次，当visit[n][k]不是-1，也就是说，在某处剪切是最佳的，我们在进行切割后重新分配{}，即n=n-i-1，并将结果cut存储在cuts数组中。在
• 最后，cuts将包含导致最优解的精确切割。在

请注意，您的问题中出现的伪代码在递归关系中使用的变量方面有点不正确。q用于存储DP二维数组和整数-1。j在自下而上的DP中根本没有使用，而是被常数n代替。q[j][k]未初始化。不过，总的想法是正确的。在