杆切割-动态规划
问题陈述
棒材切割的问题如下.给定一根长度为n英寸的棒子和一张i = 1, 2, 3,....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吗？当p未更新为新值时，我们为什么要使用q = max(q, p[j] + r[i-j-1])？
回答 3
Stack Overflow用户
发布于 2016-07-22 10:39:30
您应该使用两个不同的数组r和p，因为它们的含义完全不同。p[i]值告诉您，一个完整的(而不是裁剪的) i+1板的成本是多少。价值r[i]告诉你，你能赚多少钱，一个板的长度i+1 (完整或切分)。这些值并不相同。例如，在您的示例中，您有p[3] = 9，但是有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]);Stack Overflow用户
发布于 2016-07-22 09:44:19
如果我正确理解了这个问题，那么就不可能将r从实现中删除。显然，r的语义是
r[i] = maximum profit attainabble by cutting a rod of length i
into pieces of the lengths 1,...,n它需要在内部循环中访问。内循环中的递归关系转化为
q = the more profitable choice between not cutting a rod of length j
and cutting a rod of length j (in which case we take p[j] as
profit plus the maximum attainable profit of cutting the remaining
rod, which has length j-i)这意味着r中的信息是评估所必需的。
Stack Overflow用户
发布于 2016-07-22 09:59:03
不需要在内循环中使用辅助数组的棒状切割问题，并且只迭代一半。
#include <stdio.h>
#include <limits.h>
int max(int a,int b)
{
return a>b?a:b;
}
int cut_rod(int p[],int n)
{
int q=0;
int r[n+1]; // Auxiliary array for copying p and appending 0 at index 0
int i,j;
if(n<0)
return 0;
else
{
r[0]=0;
for(i=0;i<n;i++)
r[i+1]=p[i];
for(i=1;i<=n+1;i++)
{
q=INT_MIN;
for(j=0;j<=i/2;j++)
q=max(q,r[j]+r[i-j-1]);
r[i-1]=q;
}
}
return r[n];
}
int main()
{
int p[]={1,5,8,9,10,17,17,20,24,30};
int n=sizeof(p)/sizeof(int);
int val;
val=cut_rod(p,n);
printf("%d",val);
return 0;
}https://stackoverflow.com/questions/38522640
复制相似问题
腾讯云开发者
