自己做网站到哪里去接广告/电子商务网站设计方案
动态规划之钢条切割问题：
问题描述：
假定我们知道sering公司出售一段长度为I英寸的钢条的价格为pi(i=1,2,3….)钢条长度为整英寸如图给出价格表的描述
| 长度i | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| 价格p[i] | 1 | 5 | 8 | 9 | 10 | 17 | 17 | 20 | 24 |
问题分析：
4英寸钢条为例：
v 如果一个最优解将钢条切割为k段（1<=k<=n）,那么最优切割方案：
最大收益：
v 对于 rn(n>=1)，最优切割收益
v 最优子结构性质：问题的最优解由相关子问题的最优解组合而成，而这些子问题可以独立求解。
v 钢条切割问题的进一步简化：
v 自顶向下的递归实现
v 分析运行时间
v 钢条切割的递归调用树：
v
v 使用动态规划方法求解：对每个子问题只求解一次并且把结果保存下来，如果随后再次需要此子问题的解，只需要查找保存的结果，而不必重新计算。
v 自顶向下方法：
v 自底向上方法：
自顶向下和自底向上算法具有相同的渐近运行时间
v 子问题图：是一个有向图，每个顶点唯一的对应一个子问题。若求子问题x的最优解需要直接用到子问题y的最优解，那么在子问题图中会有一条从子问题x的顶点到从子问题y的顶点的有向边。
v N=4时钢条切割问题的子问题图：
v 重构解
数组s：求解规模为j的子问题时将第一段钢条的最优切割长度i保存在s[j]中。
v 输出切割方案：
v 调用 PRINT_CUT_ROD_SOLUTION(P,N)
会返回下面的数组：
v
------------------------------以上算法C++语言的实现------------------------------------------------
#define MinNumber -200
int CUT_ROD(int p[],int n)
{
int q;
if(n==0)
return0;
q=MinNumber;
for(inti=1;i<=n;i++)
{
q=max(q,p[i]+CUT_ROD(p,n-i));
}
return q;
}
//提升性能加入备忘机制
#define Maxnum 20
#define Minnum -200
//自底向上版本
int Bottom_UP_ROD(int p[],int n,int r[])
{
int q;
for(inti=1;i<=n;i++)
r[i]=Minnum;
r[0]=0;
for(intj=1;j<=n;j++)
{
q=Minnum;
for(inti=1;i<=j;i++)
{
q=max(q,p[i]+r[j-i]);
}
r[j]=q;
}
returnr[n];
}
int MEMOIZED_CUT_ROD_AUX(int p[],int n,int r[])
{
int q;
if(r[n]>=0)
returnr[n];
if(n==0)
q=0;
else
{
q=Minnum;
for(inti=1;i<=n;i++)
q=max(q,p[i]+MEMOIZED_CUT_ROD_AUX(p,n-i,r));
}
r[n]=q;
return q;
}
void MEMOIZED_CUT_ROD(int p[],int n)
{
intr[Maxnum];
for(inti=1;i<=n;i++)
r[i]=Minnum;
}
//DOWN_UP_ROD扩展版本
void EXTEND_DOWN_UP_ROD(int r[],int s[],int p[],intn)
{
r[0]=0;
for(intj=1;j<=n;j++)
{
intq=Minnum;
for(inti=1;i<=j;i++)
{
if(q0)
{
cout<<<",";
n=n-s[n];
}
cout<