动态规划 - 最大切削和实际解决方案的杆切削问题

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

正如您所说，您已经拥有最佳解决方案，此答案仅包括如何回溯确切的解决方案（每个步骤进行的切割）。

存储候选剪辑的长度= n和最大剪切= 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

Explanation

• 我们可能没有最大化解决方案的削减。在这种情况下，我们初始化visit[n][k] = -1。
• 每次，我们都有候选人在n切割长度为length=i+1的杆，即。我们可以通过削减得到更好的价格，我们将相应的切割存储在另一个二维阵列中。

重建解决方案

使用这个2-d数组（visit[n][k]），回溯跟踪精确的切割，你可以使用下面的伪代码（我故意避免代码，因为你提到你不需要它）。

cuts = []
while k > 0:
  i = visit[n][k]
  if i != -1
    // If there is a cut
    cuts.push(i + 1)
    n = n - i - 1
  k = k - 1

Explanation

• 我们从k迭代到0。
• 每次，当visit[n][k]不是-1，即。切割到某处是最佳的，我们在切割后重新分配n，即。 n = n - i - 1并将得到的cut存储在数组cuts中。
• 最后，cuts将包含导致最佳解决方案的确切切割。

请注意，在递归关系中使用的变量方面，您的问题中存在的伪代码略有不正确。 q用于存储DP 2-d阵列以及整数-1。 j根本不用于自下而上的DP，而是用常量n取代。 q[j][k]未初始化。但是，一般的想法是正确的。