【动态规划】钢条切割-白红宇

【动态规划】钢条切割

阅读量：2355 次

发布时间：2019-05-10

本文共 6506 字，大约阅读时间需要 21 分钟。

花了几天的时间钻研算法导论里的动态规划，做个总结。首先，算法导论真是经典，可惜水平有限，于是乎忽略了一些推理与数学理论，留着有机会再深入，其次可能自己的理解不是很到位，有错误的地方欢迎提出，谢谢

。

动态规划（dynamic programming）与分治算法相似，都是通过组合子问题的解来求解原问题(在这里，“programming”指的是一种表格法，并非编写计算机程序)。

一、与分治算法区别：

1.子问题是否重叠性

①分治算法将问题划分为互不相交的子问题，递归地求解子问题，再将它们的解组合起来，求出原问题的解。

②动态规划应用于子问题重叠的情况，即不同子问题具有公共的子子问题（子问题的求解释递归进行的，将其划分为更小的子子问题）

2.子问题是否重复求解

①分治算法会反复求解那些公共子问题。

②动态规划对每个子子问题只求解一次，将其解保存在一个表格中。(空间换时间)

二、动态规划的求解步骤

1.刻画一个最优解的结构特征。

2.递归地定义最优解的值。

3.计算最优解的值，通常采用自底向上的方法。

4.利用计算出的信息构造一个最优解。

步骤1~3是动态规划算法求解问题的基础，如果我们仅仅需要一个最优解的值，而非解本身，可以忽略步骤4。如果确实要做步骤4，有时就需要在执行步骤3的过程中维护一些额外信息，以便用来构造一个最优解。

三、钢条切割

第一个应用动态规划的例子是求解一个如何切割钢条的简单问题。

Serling公司购买长钢条，将其切割为短钢条出售，切割工序本身没有成本支出。公司管理层希望知道最佳的切割方案。假定我们知道Serling公司出售一段长度为i英寸的钢条的价格为pi(i=1,2,..,单位为美元)。钢条的长度均为整英寸，下图给出一个价格表的样例。

钢条切割问题时这样的：给定一段长度为n英寸的钢条和一个价格表pi(i=1,2,...,n),求切割钢条方案，使得销量收益rn最大,注意，如果长度为n英寸的钢条的价格pn足够大，最优解可能就是完全不需要切割。

考虑n=4的情况，可以知道切割为p2+p2=5+5=10的收益（其中长度为n英寸的钢条共有2^（n-1）种不同的切割方案，当然我们可以按照长度非递减的顺序切割小段钢条，切割方案会少得多），为最优解。

对于上述价格表样例，我们可以观察所有最优收益值ri(i=1,2,..,10)及对应的最优切割方案：

r1=1，切割方案1=1（无切割）
r2=5，切割方案2=2（无切割）
r3=8，切割方案3=3（无切割）
r4=10，切割方案4=2+2
r5=13，切割方案5=2+3
r6=17，切割方案6=6（无切割）
r7=18，切割方案7=1+6或7=2+2+3=4+3
r8=22，切割方案8=2+6
r9=25，切割方案9=3+6
r10=30，切割方案10=10（无切割）

更一般地，对于rn(n>=1)，我们可以用更短的钢条的最优切割收益来描述它：

rn=max（pn,r(1)+r(n-1),r(2)+r(n-2),...,r(n-1)+r(1)） （这里可以优化一下，例如7=1+6和7=6+1其实是一样的，故到r(n/2)+r(n-n/2)时即可）

其中第一个参数pn对应不切割，直接出售长度为n英寸的钢条方案。其他n-1个参数对应另外n-1种方案；对应每个i=1,2,...,n-1,首先将钢条切割为长度为i和n-i的两段，接着求解这两段的最优切割收益ri和r(n-i)（每种方案的最优收益为两段的最优收益之和）。

由于无法预知哪种方案会获得最优收益，我们必须考察所有可能的i，选取其中收益最大者。

注意到，为了求解规模为n的原问题，我们先求解形式完全一样，但规模更小的子问题。即当完成首次切割后，我们将两段钢条看成两个独立的钢条切割问题实例。我们通过组合两个相关子问题的最优解，并在所有可能的两段切割方案中选取组合收益最大者，构成原问题的最优解。我们称钢条切割问题满足最优子结构(optimal substructure)性质：问题的最优解由相关子问题的最优解组合而成，而这些子问题可以独立求解。

递归方法求解最优钢条切割问题

除了上述求解，钢条切割问题还存在一种相似的但更为简单的递归求解：我们将钢条从左边切割下长度为i的一段，只对右边剩下的长度为n-i的一段继续进行切割（递归求解），对左边的一段不再进行切割。

即问题分解的方式为：将长度为n的钢条分解为左边开始一段，以及剩下部分继续分解的结果。这样不做任何切割方案就可以描述为：第一段的长度为n，收益为pn,剩余部分长度为0，对应的收益为r0=0。于是我们可以得到上述公式的简化版本：

rn=max（pi+r(n-i)） (1<=i<=n)

在此公式中，原问题的最优解只包含一个相关子问题（右端剩余部分）的解，而不是两个。

自顶向下递归实现

下面的过程实现了公式的计算，它采用的是一种直接的自顶向下的递归方法。(原文是伪代码，这里是C++语言的实现)

int CUT_ROD(int *p,int n) /* 过程CUT_ROD以价格数组p[1..n]和整数n为输入，返回长度为n的钢条的最大收益 */   {       if(n==0) return 0;    /* 若n=0，不可能有任何收益，返回0 */	   int q=INT_MIN;        /* 将最大收益q初始化为负无穷，以便for循环可以正确计算 */	   for(int i=1;i<=n;i++) q=max(q,p[i]+CUT_ROD(p,n-i));	   return q;             /* 返回计算结果 */   }

但是用递归实现，一旦输入规模稍微变大，程序运行时间会变得相当长，例如，对n=40,程序至少运行好几分钟(下面会给出性能对比)，很可能超过一个小时。实际上，你会发现，每当将n增大1，程序运行时间差不多就会增加1倍。

至于效率为什么那么差，原因在于CUT_ROD反复地用相同的参数值对自身进行递归调用，即它反复求解相同的子问题，下图显示了n=4时的调用过程：CUT_ROD(p,n)

对于i=1,2,...n调用CUT_ROD(p,n-i),等价于对j=01,...,n-1调用CUT_ROD(p,j)。当这个过程递归展开时，它所做的工作量（用n的函数的形式描述）会爆炸性的增长。

这棵递归调用树显示了n=4时，CUT_ROD(p,n)的递归调用过程。每个结点的标号为对应子问题的规模n，因此，从父结点s到子节点t的边表示从钢条左端切下长度为s-t的一段，然后继续

递归求解剩余的规模为t的子问题。从根结点到叶结点的一条路径对应长度为n的钢条的2^(n-1)种切割方案之一。一般来说这棵递归树共有2^n个结点，其中有2^(n-1)个叶子结点。

分析运行时间，T(n)=2^n，CUT_ROD为运行时间为n的指数函数

使用动态规划方法求解最优钢条切割问题

现在展示如何将CUT_ROD转换为一个更高效的动态规划算法。

动态规划方法的思想如下所述。我们已经看到，朴素递归算法之所以效率很低，是因为它反复求解相同的子问题。因此，动态规划方法仔细安排求解顺序，对每个子问题只求解一次，并将结果保存下来。

如果随后再次需要此子问题的解，只需查找保存的结果，而不必计算。因此，动态规划方法是付出额外空间来节省计算时间，是典型的时空权衡(time-memorytrade-off)的例子。而时间上的节省可能使非常巨大的：可能将一个指数时间的解转换为一个多项式时间的解。如果子问题的数量是输入规模的多项式函数，而我们可以在多项式时间内求出每个子问题，那么动态规划方法的总运行时间就是多项式阶的。

动态规划有两种等价的实现方法，下面以钢条切割为例展示这两种方法。

第一种方法称为带备忘的自顶向下法（top-down with memoization）。此方法仍按自然的递归形式编写过程，但过程会保存每个子问题的解（通常保存在一个数组或散列表中）。当需要一个子问题的解时，过程首先检查是否已经保存过此解。如果是直接返回保存的值，从而节省了计算时间；否则，按通常方式计算这个子问题。我们称这个递归过程是带备忘的（memoized），因为它“记住”了之前已经计算出的结果。

第二种方法称为自底向上法（bottom-up method）。这种方法一般需要恰当定义子问题“规模”的概念，使得任何子问题的求解只依赖于“更小的”子问题的求解。当求解某个子问题时，它所依赖的那些更小的子问题都已求解完毕，结果已经保存。每个子问题只需求解一次，当我们求解它（也是第一次遇见它）时，它的所有前提子问题都已求解完成。

两种方法得到的算法具有相同的渐近运行时间，仅有的差异是在某些特殊情况下，自顶向下方法并未真正递归地考察所有可能的子问题。由于没有频繁的递归函数调用开销，自底向上方法的时间复杂性函数通常具有更小的系数。

下面给出的是自顶向下CUT-ROD过程的c++语言代码，加入了备忘机制：

int MEMOIZED_CUT_ROD(int *p,int n)	{		int *r=new int[n+1];		for(int i=0;i<=n;i++) r[i]=INT_MIN;        /* 初始化为负无穷，这是一种常见的表示“未知值”的方法（已知的收益总是非负值）*/		return MEMOIZED_CUT_ROD_AUX(p,n,r);	}	int MEMOIZED_CUT_ROD_AUX(int *p,int n,int *r)	{		int q;		if(r[n]>=0) return r[n];         /* 若所需值已知，直接返回 */		if(n==0) q=0;                    /* 否则计算 */ 		else                              		{			q=INT_MIN;			for(int i=1;i<=n;i++) q=max(q,p[i]+ MEMOIZED_CUT_ROD_AUX(p,n-i,r));		}		r[n]=q;                         /* 存入r[n] */		return q;	}

自底向上版本更为简单：

int BOTTOM_UP_CUT_ROD(int *p,int n)	{		int q;		int *r=new int[n+1];		r[0]=0;		for(int i=1;i<=n;i++)		{			q=INT_MIN;			for(int j=1;j<=i;j++) q=max(q,p[j]+r[i-j]); /* 内for循环的迭代次数构成一个等差数列。 */			r[i]=q;		}		return r[n];	}

自底向上算法和自顶向下算法具有相同的渐近运行时间。

重构解

前面给出的钢条切割问题的动态规划算法返回最优解的收益值，但并未返回解本身（一个长度列表，给出切割后每段钢条的长度）。我们可以扩展动态规划算法，使之对每个子问题不仅保存最优收益值，还保存对应的切割方案。利用这些信息，我们就能输出最优解。

下面给出的是BOTTOM_UP_CUT_ROD的扩展版本，它对长度为i的钢条不仅计算最大收益值ri，还保存最优解对应的第一段钢条的切割长度si：

void EXTENDED_BOTTOM_UP_CUT_ROD(int *p,int n,int *r,int *s) /* 原文是返回两个数组，这里通过传入两个数组完成同样操作 */	{		int q;		r[0]=0;		for(int i=1;i<=n;i++) 		{			q=INT_MIN;			for(int j=1;j<=i;j++)			{				if(q

此过程与BOTTOM_UP_CUT_ROD很相似，差别只是在需要额外的数组s,并在求解规模为i的子问题时将第一段钢条的最优切割长度j保存在s[i]中。

下面过程输出长度为n的钢条的完整最优切割方案：

void PRINT_CUT_ROD_SOLUTION(int *p,int n)	{		int *r=new int [n+1];		int *s=new int [n+1];		EXTENDED_BOTTOM_UP_CUT_ROD(p,n,r,s);		while(n>0)		{			cout<

对于前面给出的钢条切割实例，EXTENDED_BOTTOM_UP_CUT_ROD(p,10,r,s),中数组r和数组s如下所示：

下面给出完整的代码实现，以及递归与动规解法的效率对比。

#include
   
    #include
    
     const int INT_MIN=-2147483647 - 1;using namespace std;/*自顶向下递归*/int CUT_ROD(int *p,int n) {       if(n==0) return 0;   	   int q=INT_MIN;        	   for(int i=1;i<=n;i++) q=max(q,p[i]+CUT_ROD(p,n-i));	   return q;             }/*带备忘的自顶向下法*/ int MEMOIZED_CUT_ROD_AUX(int *p,int n,int *r){	int q;	if(r[n]>=0) return r[n];         /* 若所需值已知，直接返回 */	if(n==0) q=0;                    /* 否则计算 */ 	else                              	{		q=INT_MIN;		for(int i=1;i<=n;i++) q=max(q,p[i]+ MEMOIZED_CUT_ROD_AUX(p,n-i,r));	}	r[n]=q;                         /* 存入r[n] */	return q;}int MEMOIZED_CUT_ROD(int *p,int n){	int *r=new int[n+1];	for(int i=0;i<=n;i++) r[i]=INT_MIN;        /* 初始化为负无穷，这是一种常见的表示“未知值”的方法（已知的收益总是非负值）*/	return MEMOIZED_CUT_ROD_AUX(p,n,r);}/*自底向上法*/int BOTTOM_UP_CUT_ROD(int *p,int n){	int q;	int *r=new int[n+1];	r[0]=0;	for(int i=1;i<=n;i++)	{		q=INT_MIN;		for(int j=1;j<=i;j++) q=max(q,p[j]+r[i-j]); /* 内for循环的迭代次数构成一个等差数列。 */		r[i]=q;	}	return r[n];}/*重构解*/int EXTENDED_BOTTOM_UP_CUT_ROD(int *p,int n,int *r,int *s) /* 原文是返回两个数组，这里通过传入两个数组完成同样操作 */{	int q;	r[0]=0;	for(int i=1;i<=n;i++) 	{		q=INT_MIN;		for(int j=1;j<=i;j++)		{			if(q

当n=30时