算法导论读书笔记之钢条切割问题
算法导论读书笔记之钢条切割问题巧若拙（欢迎转载，但请注明出处：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;
}
