算法导论读书笔记之钢条切割问题
巧若拙（欢迎转载，但请注明出处：http://blog.）
给定一段长度为n英寸的钢条和一个价格表 pi (i=1,2, …,n)，求切割钢条的方案，使得销售收益rn最大。注意，如果长度为n英寸的钢条价格pn足够大，最优解可能就是完全不需要切割。
若钢条的长度为i，则钢条的价格为Pi，如何对给定长度的钢条进行切割能得到最大收益？
长度i　   1    2    3   4     5      6      7     8      9      10
价格Pi   1    5    8   9    10     17    17    20    14     30
 
i = 1时，钢条不可切割，r[1]= 1；
i = 2时，钢条可分割为1+ 1，其价格为2。若不分割（0 + 2），价格为5。即r[2] = 5；
i = 3时，钢条可分割为0+ 3，1 + 2。r[3] = 8；
同理可得：
r[4] = 10（2+ 2）；
r[5] = 13（2+ 3）；
r[6] = 17（0+ 6）；
r[7] = 18（1+ 6或4+ 3=> 2 + 2 + 3）；
.......
我们可以发现，长度为7时，将其切割为长度4与长度3的钢条，并对两个钢条分别求最优解：长度4的最优解为r[4] = 10（2 + 2），长度3的最优解为r[3] = 8，即可得r[7] =r[4]+ r[3] =>原问题的最优解等于子问题的最优解之和的最大值
     我们将钢条左边切割下长度为 i 的一段，只对右边剩下的长度为 n-i 的一段继续进行切割（递归求解），对左边的一段不再进行切割。即问题分解的方式为：将长度为n 的钢条分解为左边开始一段，以及剩余部分继续分解的结果。这样，不做任何切割的方案就可以描述为：第一段的长度为n ，收益为 pn，剩余部分长度为0，对应的收益为r0=0。于是公式的简化版本：
 
因此，在计算r[i]时，所求值即为r[0] +r[i]，r[1]+ r[i- 1]，r[2]+ r[i- 2]，...  ，r[i- 1] +r[1] 之间的最大值，而在动态规划中，r[0]——r[i - 1]的值在计算r[i]之前已经保存好了，进行少量的运算便能取得最优结果。

使用动态规划算法求解最优钢条切割问题有两种等价的实现方法。
第一种方法称为带备忘的自顶向下法。此方法按照递归方式编写过程，但过程会保存每个子问题的解——用数组r[i]记录总长度为i的钢管的最大收益值。当需要一个子问题的解时，过程首先检查是否已经保存过此解，如果是，直接返回保存的值，否则递归计算这个子问题。
    第二种方法称为自底向上法，这是动态规划的常用方法，这种方法需要我们将子问题按照规模排序，按由小到大的顺序进行求解——在本题中即按i从1到n的顺序求解。每个子问题只需求解一次，并及时把结果记录下来，以便后面调用。
两种方法得到的算法具有相同的渐进运行时间，仅有的差异是在某些特殊情况下，自顶向下方法并未真正递归的考察所有可能的子问题。由于没有频繁的递归函数调用的开销，自底向上方法的时间复杂性函数通常具有更小的系数。
代码如下：
#include<stdio.h>
#include<stdlib.h>

#define MAX 20001   //最大长度
#define INFINITY -999999   //负无穷大

void PrintCutRodSolution(int p[], int n);//自底向上法
void BottomUpCutRod(int p[], int r[], int s[], int n);//记录总长度为i的钢管的最大收益值r[i]及其第一段钢条的切割长度s[i]
void MemoizedCutRod(int p[], int n);//带备忘的自顶向下法
int MemoizedCutRodAux(int p[], int r[], int s[], int n);//递归计算r[i]的值

int main()
{
    int p[MAX] = {0};
    int i, n = 50;
   
    for (i=1; i<=n; i++)//随机获取长度价格，但确保长的比短的价值高
    {
        do{
            p[i] = (i>4)? (p[i-4] + rand()%20+1) : rand()%20+1;
        }while (p[i] <= p[i-1]);
        printf("%7d", p[i]);
    }
   
    printf("\n");
    PrintCutRodSolution(p, n);//自底向上法
    printf("\n");
    MemoizedCutRod(p, n);//带备忘的自顶向下法

    return 0;
}

void PrintCutRodSolution(int p[], int n)//自底向上法
{
    int r[MAX] = {0};//r[i]记录总长度为i的钢管的最大收益值  
    int s[MAX] = {0};//s[i]记录r[i]对应的第一段钢条的切割长度
    int i;
   
    BottomUpCutRod(p, r, s, n);
//    printf("最大价值:\n");
//    for (i=1; i<=n; i++)
//    {
//        printf("%2d:%3d  ", r[i], s[i]);
//    }
//    printf("\n");
   
    printf("最大价值: %d\n", r[n]);
    printf("切割方案:\n");
    while (n > 0)
    {
        printf("%d\t", s[n]);
        n -= s[n];
    }
    printf("\n");
}

void BottomUpCutRod(int p[], int r[], int s[], int n)//记录总长度为i的钢管的最大收益值r[i]及其第一段钢条的切割长度s[i]
{
    int i, j, max;
   
    r[0] = 0;
    for (i=1; i<=n; i++)//钢管总长度为i
    {
        max = INFINITY;
        for (j=1; j<=i; j++)
        {
            if (max < p[j] + r[i-j])//如果分解成长度j和长度i-j两部分能获得更大收益，则更新最大收益值max，并记录对应的第一段钢条的切割长度s[i]
            {
                max = p[j] + r[i-j];
                s[i] = j;
            }
        }
        r[i] = max; //记录总长度为i的钢管的最大收益值
    }
}

void MemoizedCutRod(int p[], int n)//带备忘的自顶向下法
{
    int r[MAX] = {0};//r[i]记录总长度为i的钢管的最大收益值  
    int s[MAX] = {0};//s[i]记录r[i]对应的第一段钢条的切割长度
    int i;
   
    for (i=0; i<=n; i++)//初始化
        r[i] = INFINITY;
   
    printf("最大价值: %d\n", MemoizedCutRodAux(p, r, s, n));
    printf("切割方案:\n");
    while (n > 0)
    {
        printf("%d\t", s[n]);
        n -= s[n];
    }
    printf("\n");
}

int MemoizedCutRodAux(int p[], int r[], int s[], int n)//递归计算r[i]的值，并同时记录s[i]的值
{
    int i, max, temp;
   
    if (r[n] >= 0)//已经记录过了就不再重复计算
        return r[n];
    if (n == 0)
        max = 0;
    else
    {
        max = INFINITY;
        for (i=1; i<=n; i++)
        {
            temp = p[i] + MemoizedCutRodAux(p, r, s, n-i);//计算把钢条分为长度为i和n-i两部分所得到的最大收益值
            if (temp > max)//更新最大收益值并记录对应s[i]的值  
            {
                max = temp;
                s[n] = i;
            }
        }
    }

    return r[n] = max;
}