杆切割-动态编程 [英] Rod Cutting - Dynamic Programming

问题描述

问题陈述

切割棒的问题如下。给定长度为 n 英寸的棒并以价格表 Pi 表示 i = 1， 2，3，.... n ，确定最大的收入 Rn ，方法是切割杆并出售零件。请注意，如果长度为 n 的棒的价格 Pn 足够大，则最佳解决方案可能不需要在

The rod-cutting problem is the following. Given a rod of length n inches and a table of prices Pi for i = 1, 2, 3,....n, determine the maximum revenue Rn obtain- able by cutting up the rod and selling the pieces. Note that if the price Pn for a rod of length n is large enough, an optimal solution may require no cutting at all.

考虑 n = 4 的情况。图中显示了截断4英寸长的杆的所有方法，包括根本没有切口的方法。我们看到将4英寸的杆切成2个2英寸的块会产生收入 P2 + P2 = 5 + 5 = 10 ，这是最佳选择。

Consider the case whenn=4. Figure shows all the ways to cut up a rod of 4 inches in length, including the way with no cuts at all. We see that cutting a 4-inch rod into two 2-inch pieces produces revenue P2+P2=5+5=10, which is optimal.

下面的代码是为解决方案构建自底向上的方法

The below code is a bottom-up approach of building the solution for rod-cutting.

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]？
为什么当p未更新为新值时，为什么使用 q = max（q，p [j] + r [ij-1]）？ p>

Why do we need an auxiliary array r[n+1]? Couldn't the problem be solved only by using just array p? Is it used because we cannot access p[-1] when we are cutting of rod length n and 0? Why are we using q = max(q, p[j] + r[i-j-1]) when p is not updated to new values?

推荐答案

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

You should use two different arrays r and p, because their meaning is completely different. The value p[i] tells you, how much a complete (not cut) board of length i+1 costs. The value r[i] tells you, how much profit you can make with a board of length i+1 (complete or cut into pieces). These values are not the same. For instance in you example you have p[3] = 9, but r[3] = 10, because you can cut the board of length 4 into two smaller pieces of length 2. Keeping the two different meanings in separate arrays is most always a good idea. (Except if you have very tight memory restrictions)

此外，在实践中，您可能不会出售长度为100的板。但是您可能想知道最佳利润，您可以通过切割来制作这种尺寸的木板。如果只有一个阵列，则必须将其放大。根据您的语言选择，这还可能涉及创建第二个数组并复制第一个数组。因此，简单地使用第二个数组会更容易。

Also, in practice you will likely not sell boards of length 100. But you might want to know the optimal profit, that you can make with a board of this size by cutting it. If you only have one array, you would have to enlarge it. Depending one your language choice this also might involve creating a second array and copying the first array. So it would be easier to simply use a second array.

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

Notice, that it is possible though (if n is smaller than the langth of the array p). A simple solution that uses only one array would be (using one-indexed):

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]);

这篇关于杆切割-动态编程的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！