棒材切割 - 动态规划

问题陈述

棒材切割问题如下。给定一根长度为n英寸和价格表Pi for i = 1, 2, 3,....n，确定最大收益Rn可以通过切割棒并出售碎片来获得。请注意，如果价格Pn对于一根长度的杆n足够大，最佳解决方案可能根本不需要切割。

考虑以下情况：n=4。图中显示了切割 4 英寸长的杆的所有方法，包括根本不切割的方法。我们看到将一根 4 英寸的棒材切割成两块 2 英寸的部件会产生收入P2+P2=5+5=10，这是最优的。

下面的代码是构建棒切割解决方案的自下而上的方法。

for (i = 1; i<=n; i++)
{
   int q = INT_MIN;
   for (j = 0; j < i; j++)
       q= max(q, p[j] + r[i-j-1]);
   r[i] = q;
}
return val[n];

为什么需要辅助数组r[n+1]？仅使用数组不能解决问题吗p？使用它是因为当我们切割长度为 n 和 0 的杆时我们无法访问 p[-1] 吗？ 我们为什么使用q = max(q, p[j] + r[i-j-1])当 p 没有更新为新值时？

您应该使用两个不同的数组r and p，因为它们的含义完全不同。价值p[i]告诉您完整的（未切割的）板的长度是多少i+1成本。价值r[i]告诉你，你可以用一块长度的板赚取多少利润i+1（完整或切成碎片）。这些值并不相同。例如在你的例子中你有p[3] = 9, but r[3] = 10，因为你可以切割长度的板4分成两个较小的长度2。将两种不同的含义保留在单独的数组中总是一个好主意。 （除非您的内存限制非常严格）

另外，实际上您可能不会出售长度为 100 的板材。但您可能想知道通过切割这种尺寸的板材可以获得的最佳利润。如果只有一个数组，则必须扩大它。根据您选择的语言，这还可能涉及创建第二个数组并复制第一个数组。因此，简单地使用第二个数组会更容易。

请注意，尽管如此（如果n小于数组的长度p）。一种仅使用一个数组的简单解决方案是（使用单索引）：

int p[]={0,1,5,8,9,10,17,17,20,24,30};
int n = 4;
for (int i = 1; i <= n; i++)
{
    for (int j = 1; j <= i/2; j++)
        p[i] = max(p[i], p[j] + p[i - j]);
}
printf("%d\n", p[n]);