动态规划之钢条切割问题

在看这张之前，最好看看我写的动态规划详解，里面都是讲理论基础，我下面的分析都是在此基础上进展的。

钢条切割问题:

给定一段长度为n英寸的钢条和一个价格表Pi( i=1, 2, ..., n ),求切割钢条方案,使得销售收益最大.

例如:

长度i	1	2	3	4	5	6	7	8	9	10
价格Pi	1	5	8	9	10	17	17	20	24	30

依旧根据DP算法四个步骤来分析：

①.描述最优解的结构。

首先求解这些问题要用到递归思想为铺垫，因此将元素个数从n向下开始考察。长度为n，首先做一次选择，在第i个位置上切割一次，并假定为最优解。此时最优解由（1->i）和（i+1 ->n）两个子问题的最优解来实现。可以写出Rn=max(Ri+Rn-i),1<=i<=n且R0=0。通过分析可知求解全部子问题为R1+Rn-1,....,Rn-1+R1,Rn。很多是对称的，因此表达式可以优化为Rn=max(Pi+Rn-i),1<=i<=n且R0=0。对于每一个i值，只需求解一个子问题Rn-i即可。

②.递归定义最优解的值。

上面已经给出了表达式Rn=max(Pi+Rn-i),1<=i<=n且R0=0。根据此表达式来构造备份数组以及重构最优值数组。并根据此表达式编写程序。

③.按自底而上的方式计算最优解的值。

先定义备份数组，由于表达式右边是Rn-i，需要的是长度为n-i时的最优值，因此定义数组R[n]，保存长度为i时的最优值。

④.由计算出的结果创造一个最优解。

为了构造最优值，就要保存切割信息，当求长度为j的Rj=max(Pi+Rj-i)时，i从1到j。由于是求最大值，因此保存Rj取得最大值是的切割点i。并且写代码是，这种求最大值最小值，可以先设置一个中间变量，如果每一次遍历求解的值先保存在中间变量中，当中间变量更优时，更新备份数组。此时也更新切割结点。

自顶向下的方法：不带备忘和带备忘

//自顶向下的递归
CUT-ROD(p,n)
{
    if(n==0)
        return 0;
    temp = q =-1000;
    for(int i=1;i<=n;i++){  //取值范围由递归表达式的变量范围而来
        temp = p[i]+CUT-ROD(P,n-i); //求解max()问题，转化成先存储在一个临时变量里面，然后再更新
        if(temp > q)
            q = temp;
    }
    return q;
}


//带备份的自顶向下的递归
MEMOIZED-CUT-ROD(p,n)
{
    int r[n+1];
    for(int i=0;i<=n;i++)
        r[i] = -10000;
    return MEMOIZED-CUT-ROD-AUX(p,n,r);
}

MEMOIZED-CUT-ROD-AUX(int p[],int n,int r[])
{
    if(r[n]>=0)         //不同点1，入口时就判断存储值是否有效。有效立即返回
        return r[n];
    if(n==0)            //这里是对r[0]赋值，之后r[0]的返回有上面语句来完成。
        q = 0;
    else{
        q = -10000;
        for(int i=1;i<=n;i++){  //遍历形式与普通递归方法一模一样
            temp = p[i] + MEMOIZED-CUT-ROD-AUX(p,n-i,r);
            if(temp > q)
                q = temp;
        }
    }
    r[n] = q;   //不同点2，出口时，对数组存储进行更新。
    return r[n];
}
           

自底向上的方法

//自底向上的方法
BOTTOM-UP-CUT-ROD(p,n)
{
    int r[n+1],s[n+1];
    r[0] = 0;   //对基本的一定要赋值！最安全的做法是将整个数组初始化为合适值0、正无穷、负无穷
    for(int j=1;j<=n;j++){
        q = -10000;
        for(int i=1;i<=j;i++){
            if(q < p[i]+r[n-i]){
                q = p[i]+r[n-i];
                s[j] = i;
            }
        }
        r[j] = q;
    }
    return r[]and s[];
}
           

输出切割方案

//输出切割方案
PRINT-CUT-ROD-SOLUTION(p,n)
{
    (r,s) = BOTTOM-UP-CUT-ROD(p,n);
    while(n){
        print s[n];
        n = n-s[n];
    }
}