动态规划与0-1背包问题

定义

动态规划中一个经典的问题就是0-1背包问题，0-1的意思也就是说对于每个元素/选项，只有两个选择，要么选择，要么不选择。动态规划的分析过程为：确定推导公式/状态转移方程，子元素结构/独立子结构，确定边界，保存中间数据/备忘录。

动态规划过程的核心要素就是确定推导公式，类似于初中数学上经常遇到的这样一个场景：

已知：

a(n)=a(n-1)+a(n-2);

a(0)=a(1)=1;

求解a(10)的值，过程就是：

a(10)=a(9)+a(8);

a(9)=a(8)+a(7);

......

a(2)=a(1)+a(0);

这样的计算过程大家都很熟悉，其中：a(n)=a(n-1)+a(n-2)就是所谓的状态转移方程，a(9)，a(8)就是独立的子结构，a(0)，a(1)就是边界，上面的计算过程常用的有两种方式：

(1)由下向上

计算a(2)，根据(a(2),a(1))计算a(3)...，直到得出a(10)，也就是常用的迭代方式。

while i<=10:
	a(i)=a(i-1)+a(i-2)
	i++

(2)由上向下

根据a(9),a(8)的值计算a(10)，根据a(8),a(7)的值计算a(9)...，直到a(1),a(0)，这就是所谓的递归。

f(x):
	if(x==0||x==1)	{
		return 1
	}else{
		return f(x-1)+f(x-2)
	}

迭代过程没什么好说的，观察递归过程可以发现：

a(10)

=a(9)+a(8)

=( a(8)+a(7) )+a(8)

=( a(7)+a(6) )+( a(6)+a(5) )+( a(7)+a(6) )
即递归的展开过程存在许多重复使用的元素，例如这里的a(7)、a(6)，如果继续展开会重复使用更多的a(3)、a(2)，所以如果递归的计算过程如：

f(x):
	if(x==0||x==1)	{
		return 1
	}else{
		return f(x-1)+f(x-2)
	}

则存在很多重复的计算，因为每一个f函数都会递归计算到：x==1||x==0，然后再返回数据，这里可以使用数组来保存中间结果：

f(x):
	if(x==0||x==1)	{
		return 1
	}else if(arr[x]!=0){
		return arr[x]
	}else{
		arr[x]=f(x-1)+f(x-2)
		return arr[x]
	}

避免重复的计算过程

示例

存在容量为W的背包，n个价值为v[i](0=<i<n)，占据空间为w[i](0=<i<n)的物品，每个物品取一个，问在背包容量W的条件下，最多能够装载的最大物品价值。

分析：

对于n个物品中的每一个，仅存在两种情况，即被放入背包或者不放入背包，此处将该n个物品看做数组，物品在数组中的顺序并无影响，因为每个物品的考虑情况都是完全一样的，以f(i,w)表示在w容量下，i个物品时能够获得的最大价值，则对于第i件物品，放入背包或不放入背包对最大价值的影响为：

f(i,w)=max(s1,s2);

s1=f(i-1,w-w[i])+v[i];

s2=f(i-1,w);

s1表示w容量下，将第i件物品放入背包，最大价值即为f(i-1,w-w[i])+v[i]，其中v[i]表示第i件物品的价值，f(i-1,w-w[i])表示w容量下，除去第i件之外，在容量为w-w[i]，物品数为(i-1)个的情况下的最大价值；

s2表示w容量下，不将第i件物品放入背包，容量为w，物品数为(i-1)个的情况下的最大价值

两者相比较即可获得f(i,w)的最大值，f(i,w)=max(s1,s2)即为状态转移方程，对应的边界即为只有1个物品时的最大价值

参考代码

算法1(严重不推荐)：

根据状态转移方程：f(i,w)=max( f(i-1,w-w(i))+v(i),f(i-1,w) )，i表示前i个物品，w表示空间容量，w(i)表示第i个物品的占据空间，v[i]表示第i个物品的价值

public static int method1(int n,int W){//n表示物品个数，W表示空间大小
	if(n==0){//当只有1个物品时，只需判断该物品能否放下即可
		if(W>=w[0]){//能够放入背包
			return v[0];
		}else{//不能放入
			return 0;
		}
	}else{//当多于1个物品时，按照状态转移方程计算
		if(W>=w[n]){//第i个物品可以被放入背包时，比较放入和不放入哪个价值更大
			return Math.max(method1(n-1,W),method1(n-1,W-w[n])+v[n]);
		}else{//第i个物品不能被放入背包，则直接等于不能放入的价值
			return method1(n-1,W);
		}
	}
}

该方式代码很简洁，但是没有用到备忘录，也就是中间的计算结果并没有保存，每个计算都存在极大的重复计算，以斐波那契数列为例：

private static int LEN=50;
private static long[] fib=new long[LEN+1];
public static long fibo2(int n){//使用fib数组保存中间结果
	if(n==1||n==2){
		fib[1]=1;
		fib[2]=1;
		return 1;
	}else{
		if(fib[n]==0){
			fib[n]=fibo2(n-1)+fibo2(n-2);
		}
		return fib[n];
	}
}
public static long fibo1(int n){//不保存中间结果
	if(n==1||n==2){
		return 1;
	}else{
		return fibo1(n-1)+fibo1(n-2);
	}
}

fibo1和fibo2方法都是使用递归调用获得结果，但是两者的性能差异会随着数据的增大变得异常明显，所以虽然fibo2需要额外的数据空间来保存临时结果，但是这种消耗是必需的，否则计算过程的时间将会超出忍耐。

所以算法1的代码这里严重不推荐，事实上动态规划过程中对备忘录(中间数据的保存)是必要的，后面介绍的算法2和算法3可以说明，计算是依赖或建立于临时数据之上的

算法2：

使用二维数组来保存背包问题的临时结果：

v[i]作为价值数组，w[i]作为对应的空间占据量，s[i][j]表示前i个物品，在空间容量为j时，对应的最大价值(这里多余一句，虽然i表示前i个物品，或者i个物品，但是物品的摆放顺序并不影响结果)

转移方程为：f(i,j)=max[ f(i-1,j), f(i-1,j-w(i))+v[i] )

分析这个方程，可知f(i,j)，即前i个物品在j空间的容量下对应的最大价值，依赖于两个数值：f(i-1,j),f(i-1,j-w[i])+v[i]，其实也就是说，j空间容量下，前i个物品的最大价值，只是关系于前(i-1)个物品在j空间或者小于j空间(即j-w[i])下的最大价值(这点在算法3，使用一维数组存储临时结果时也会提到)

上面是一个很水的图，但是不影响说明，(a,b,c,d,e)表示五个物品，(j1,j2,j3,j4,j5)表示容量大小，以s表示这个二维数组，则s[a][j3]表示，只有物品a，容量大小为j3时，对应的最大价值，这里需要注意:s[b][j3]表示只有[a,b]两个物品，容量为j3时的最大物品，而非只有物品b时的情况。

根据转移方程：f(i,j)<--[f(i-1,j),f(i-1,j-w[i])]，这里v[i]就不需要纳入考虑了，知道公式里有这个数值就行了，那么很明显f([a,b],j3)<--[f([a],j3),f([a],j3-w[b])]，问题到这里已经很明朗了，2个物品[a,b]的最大价值，只需要根据1个物品[a]即可获得，同理，3个物品[a,b,c]的最大价值，只需要根据2个物品[a,b]即可获得，这点类似于以前数学上的：

a(n)=a(n-1)+t;

然后又告诉你a(1)的值，只需要不断推导a(2),a(3)即可计算出最终的a(n)，这里的a(1)就是f([a],j)，只有一个物品a时，当j大于w[a]时，即a能够放入背包时，s[a][j]=v[a]，当j小于w[a]，s[a][j]=0，由此按照由上至下，由左至右的方式即可推导出最后的s[e][j5]，即f([a,b,c,d,e],j5)，即5个物品时，j5容量下的最大价值。

public static void method2(){
	for(int i=0;i<n;i++){//n表示物品个数
		for(int j=0;j<=W;j++){//W表示容量大小
			if(i==0){//只有一个物品时
				if(j>=w[i]){
					s[i][j]=v[i];
				}else{
					s[i][j]=0;
				}
			}else{//多于一个物品时
				if(j>=w[i]){//第i个物品可以被放入背包时，比较放入和不放入哪个价值更大
					s[i][j]=Math.max(s[i-1][j],s[i-1][j-w[i]]+v[i]);
				}else{//第i个物品不能被放入背包，则直接等于不能放入的价值
					s[i][j]=s[i-1][j];
				}
			}
		}
	}
}

方法2使用二维数组来存储临时数据，以增加空间消耗的方式来节省计算性能，观察上述计算过程，可以发现上述使用二维数组来保存计算结果的过程中，是按照由上向下，由左向右的方式进行计算的，这样的计算过程结合转移方程(一切核心都在转移方程中)可以发现某种规律，而这种规律的作用下，使用二维数组就显得没有必要，所以这里进一步优化空间使用，使用一维数组来保存计算结果，节省空间消耗。

算法3：

使用一维数组来保存中间计算结果，观察状态转移方程：

if(j>=w[i]){//第i个物品可以被放入背包时，比较放入和不放入哪个价值更大
	s[i][j]=Math.max(s[i-1][j],s[i-1][j-w[i]]+v[i]);
}else{//第i个物品不能被放入背包，则直接等于不能放入的价值
	s[i][j]=s[i-1][j];
}

对于第i个物品，只有当容量j>=w[i]时，才存在把第i件物品放入背包和不放入背包的问题，如果w[i]>j，则根本也不能放入背包，所以才有s[i][j]=s[i-1][j]

观察这个粗略的图：

以图中染色的点作为w[b]==j4的点，即j4容量下，刚好可以把b物品放入背包，然后进行转移方程(放入还是不放入这是个问题)的考虑，那么很明显，在b物品行，j4之前的点都同上，即：

f([a,b],j1)=f([a],j1)

f([a,b],j2)=f([a],j2)

f([a,b],j3)=f([a],j3)

也就是所谓的算法2代码中的：s[i][j]=s[i-1][j]，第i件物品不放入背包(因为放不下)

所以这里考虑的问题就是转移方程的描述：

f([a,b],j4)=max[f([a],j4),f([a],j4-w[b])+v[b]],b物品该行，j4之后数据也是这样进行计算，那么规则就出来了，观察下图：

为了避免一个搞不清楚，所以画了两个，在b行，j4及j4之后的所有值都是根据转移方程：f([a,b],j4)=max[f([a],j4),f([a],j4-w[b])+v[b]]，因为f([a],j4)和f([a],j4-w[b])都是a行中的数据，也就是说f([a,b],j4),都是根据a行，j4及j4之前的数据而得来的，也就是上图中a行的灰色区域，b行的灰色区域数据都是根据a行的灰色区域数据得来的，而b行的红色区域数据都是照搬上一行的数据，即s[b][j1]=s[a][j1],s[b][j2]=s[a][j2]，s[b][j3]=s[a][j3]，因为在j1，j2，j3的容量下b物品根本放进去背包，所以不需要根据转移方程计算。

由此得出规律，上图中的计算，知道了a行数据后，b行数据由j5开始向j1移动，j4及j4之后数据，根据a行j4及j4之前数据计算，b行j4之前数据照搬a行即可，之所以由右向左计算，而不是算法2中的由左向右计算，是因为由右向左b行数据例如s[b][j4]、s[b][j5]的数据，即使存放在a行位置上也不会有任何影响，例如把s[b][j5]计算后得到的数据存放在s[a][j5]位置上，s[b][j4]数据存放在s[a][j4]位置上，对b行接下来的计算过程如s[b][j3]、s[b][j2]等，不会产生任何影响，now you get it，所以可以在得知a行数据后，将计算获取的b行数据都存放在a行对应的位置上，同理，后面的c行数据也存放在上一行的数据上，由此得出一维数据保存计算结果。

public static void method3(){
	for(int i=0;i<n;i++){//n表示物品个数
		for(int j=W;j>=0;j--){//W表示空间容量
			if(i==0){//只有一个物品时，判断能否放入背包
				if(j>=w[i]){
					s1[j]=v[i];
				}else{
					s1[j]=0;
				}
			}else{//多于一个物品时，状态转移方程判断
				if(j>=w[i]){
					s1[j]=Math.max(s1[j],s1[j-w[i]]+v[i]);
				}else{
					s1[j]=s1[j];//这里当然不用写，不过写出来与上面对照
				}
			}
		}
	}
}

这里也就验证了之前提到，动态规划算法是建立在临时数据上的，是依赖于中间数据进行推导的