数据结构与算法21

递归、递推及动态规划

对于非负整数而言，阶乘的定义就是从1乘到自身，写成函数表达式则为 $f(n)=n!= {\begin{matrix} n×f(n-1), & n>1 \\ 1, & n=0or1 \end{matrix}$ ，要算出f(n)就得计算f(n-1)，也就得算出f(n-2)……直到要计算f(2)时我们知道f(2)=2×1=1。也就是说，求阶乘的这个问题是套娃的。想求出f(x)的值就必须把f(1)~f(n-1)的值都给算出来。我们当然可以用上面的函数表达式来自定义一个功能模块来解决这个问题——一个求f(x)的模块内部自带计算f(1)~f(n-1)的能力。然而这样做是严重浪费时间的，为什么呢？因为当机器在计算f(i)(1<i<n)时，它会计算f(1)~f(i-1)的值，而当机器在求f(i+1)的时候，它又会把f(1)~f(i)的值给算一遍。可f(1)~f(i)里面就已经包含了f(1)~f(i-1)的内容，此时求f(1)~f(i-1)显然是做无用功。下面是递归C代码：


int f(int n)
{
	return n>1?n*f(n-1):1;
}

其实算一元多项式的时候也是这个情况，我们万万不能对多项式里的元，先求高次方再求低次方进而代入，因为那样会重复很多乘方运算。但如果我们能够从最小规模的子问题开始求解，一步步自底向上推向总问题的答案，使得过去的计算能够辅助后续工作，那就大大节省了时间，美其名曰递推。先前求非负整数阶乘的代码里有太多次函数调用，需要在代码段和函数调用栈分别进行多次跳转和出入栈。为此我们可以临时记下小问题的答案，然后根据这个子问题的解求解父问题。开搞：

int f(n)
{//其实这个就是一个简单的循环语句罢了
	if(n==0||n==1)return 1;
	else{
		int lastn=1;//上一个阶乘值记录在此
		for(int i=2;i<=n;i++)
		{
			lastn*=i;
		}return lastn;//i等于n时即为最终答案
}

那什么是动态规划呢？一言以蔽之：有大量记忆的递推就叫做动态规划。（其实你混淆此二者的概念也没什么毛病。）例如上面的阶乘运算，我们也可以把过去的每一个子问题答案用一个数组记下来，而不是单纯覆盖。再比如求斐波那契数列的时候，我们也可以用一个数组记载n之前的数列内容，而非笨拙地一个函数内套两次递归，或者是覆盖。那为什么要另外占用存储空间记载这么多信息呢？如果只是算阶乘和斐波那契数列这样的问题当然也可以不这么做，但更加一般的问题中，答案的递推公式很可能是非常复杂的，所以现在把算出来的东西写下来为妙，万一以后有用呢？万一递推式不只涉及到前两项而是先前所有的呢？也不是不可能。具体如下：

int fbnq(n)//斐波那契的动态规划
{
	if(n==1||n==2)return 1;
	else{
		int f[MAX];//记得预先设置好上限
		f]0]=1;f[1]=1;
		int i;
		for(i=2;i<=n;i++)
		{
			f[i]=f[i-1]+f[i-2];
		}return f[i];
	}
}

能用动态规划解决的问题必须具备最优子结构特性，即总问题的最优解可以用子问题的最优解变出来。

离散背包

离散背包问题和连续背包问题的内容就只有一个差别：背包里放的东西数量是离散而非连续的。这就导致背包在最优解有放不满的情况。如果有一种东西的单个体积为3，那么总体积就只能是3的非负倍数倍0,3,6,9……放在一个容积为13的背包里就必然会浪费1异或2的空间，这是无法避免的。所以离散背包不能用单纯的性价比概念去贪心地计算。

问题描述：今有背包容积S，n种东西的单价w₁~w_n及其总量a₁~a_n，第i种东西的单个体积固定为v_i。把各种东西放在背包里，设法使得放进去的总价最大。出于简化，一般规定数量和单个体积都为整数。

对于每一种东西，我们首先要考虑该不该放，如果放了，该放几个？由此累积得到的最大价格多少？如果不放，累积得到的最大价格多少？两相比较取最大即可。那这里累积得到的最大价格是从全局考虑还是从已放入和当前物品的范围考虑呢？从已放入和当前物品的范围考虑，因为如果是全局考虑，那么运算过程会非常复杂，代码相对而言不好写。而如果你非要放，又怎么知道具体放几个最好？这个也要进行取最大值的操作。总之：

W_i=MAX{W_1-放,W_1-不放}

但这也引来另一个麻烦：对每一种东西放不放和放多少的思考是有限制的，因为你越是往后放东西，背包剩下的空间就越少。况且后面的方案优化对前面的行为还可能有要求。

先看对于第i种物品非要放的情况。我们设此时的空间限制为j，即要求前i种物品放入的总体积不超过j。如果要放入k个第i种东西，则带来价格w_i×k，与此同时会占用v_i×k的空间，所以，对于前(i-1)种东西来说，空间限制就是j-v_i×k。用W_a,b表示前a种东西在b的空间限制下最大可带价值，则在第i种东西必须放的时候最大可带价格为 W_1-放=W_{i-1,j-v_i×k}+w_i×k。

再看对于第i种物品非要不放的情况。很显然，此时第i种东西不带来价格且不消耗空间，于是此时累积价格最大还是上一轮的值，也就是W_1-不放=W_i-1,j。接下来，把上面的内容取最大值可得：

W_i=MAX_{0≤k≤a_i}{W_{i-1,j-v_i×k}+w_i×k,W_i-1,j}

此之谓状态转移方程。

总之，整体最大可带价格=W_n,S，至于W_a,b用什么来表示，肯定不能是函数，因为复杂度太大了，用数组为妙。

故曰：

int putnum[n+1];//记载每一种物品该放几个
int W[n+1][n+1];//最大可带价格的记录，它作为记忆的存在表明了这是一个动态规划算法
int de_bad(int w[],int a[],int v[])//默认n>1
{
	for(int i=1;i<=n;i++)//对于第i种物品
		for(int j=0;j<=S;j++)//对于j的空间限制
		{
			int m=0,maxk=0;
			for(int k=0;k<=a[i];k++)//放k个第i种东西
			{
				int w=W[i-1][j-v[i]*k]+w[i]*k;
				if(w>m){m=w;putnum[i]=k;}
			}W[i][j]=m;//取最大值记下来
		}
	return W[n][S];//整体最大可带价格
}

离散背包问题还有变体，比如令各种物品数量最多无限的完全背包问题，以及数量最多只有一个的0-1背包问题。

数学和计算机科学板块_辛酸网

数据结构与算法21