动态规划学习

在iteye看到一个问答（iteye被csdn收编了，该不算广告吧），大致是：给出一个数组和一个数字target，问数组那几个数之和与target相等。

问题看起来还挺简单。不过代码却不是一步到位立马能写出的。想着想着，突然发现这个问题和我之前发的博文中描述的问题基本是同一个类型的问题（见回溯算法复习）。于是由自然而然的想用回溯进行穷举了。不过在这个问题的回答者中，有一个人回答说用动态规划解即可，这时就勾起我的兴趣了，难道这类题本来就可以通过动态规划解答？而本文后续给出的答案表明，这是肯定的。

在介绍该题解答之前，首先简单回顾下动态规划是怎么解题的。根据算法导论所介绍，该算法一般分为4个步骤：

1. 定义最优解结构
2. 递归定义最优解的值
3. 自底向上计算最优解的值
4. 由计算出的结果构造一个最优解

下面简单的解释下这4个步骤。

1.定义最优解结构。一个问题的最优解总包含了子问题的一个最优解，或者说一个问题的最优解由子问题的最优解组成，那么就说这个问题具有最优子结构（optimal substructure）。比如，求二叉树高度的问题中（该问题本来可以只通过递归遍历数结构皆可求解，这里为例子说明方便就不用遍历方式求解，并且树结构以链表方式保存在内存中——每个子结点有引用指向父结点），一棵二叉树中根结点距离哪个叶子结点路径最长的解，就由去掉根结点后各个子树的最长路径的解组成；每个子树又具有这个最优子机构，又可以继续分解出各个子树的解。

2.递归定义最优解得值。在了解了最优子结构组成，那肯定就需要有个工具判断哪个子解更有可能成为总最优解的一部分，所以可以递归的定义解和子解的关系，以及子解的选取依据。在上面说的二叉树最深路径问题中可以得到这么一个公式：H父结点a=max（H子结点a1，H子结点a2） + 1。Hx表明x作为根结点时树的最深高度。第二部反映了两方面的内容，一个是解和子解间的关系，二是哪个比哪个好得评判标准。

3.自底向上计算最优解的值。有了问题的解和子解的关系以及评判尺度，那么，我们完全可以从最底层出发，自底向上计算出所有的解了。最低层的子解可以通过边界条件来计算获得。比如最底层的子树肯定就是深度为1或者深度为二的解了。在计算期间，还体现了动态规划的另一个特点，就是保存计算过的值，以后再遇到相同的计算式直接引用之前的结果。这样有效避免了重复计算的资源浪费，提高效率。

4.构造最优解结构。经过了第3步，我们已经可以对每个结点，根据公式能选取最优的子解了。这样只需要自上而下，我们就可以把总得最优解结构构造出来了。对于二叉树深度的例子而言，就是每个根结点依据公式，都知道哪个子结点具有最深的深度，自然就知道选择哪个结点往下走了。

所以，从上面4个步骤中可以看到，就想算法导论里面说到的，要应用动态规划，那问题就需要有2个特点。一是具有最优子结构，二是具有重复子问题。上面二叉树高度的例子中，假设父结点a到叶子结点最长路径Pa落在子节点a1上，那么，a1结点到叶子结点的最长路径也一定蕴含在Pa里面，所以说其具有最优子结构。而每个结点的最高高度肯定会在求其祖先结点被引用到（其实其结果在整个计算过程中只被引用一次，这里用二叉树高度来具有不是非常恰当），也算是有重复子问题。所以二叉树高度也可以用动态规划来解决。

那回到本文一开始的问题中，我们的数组该怎么选着其元素让所选元素之和恰好等于target值呢？我们先看下这个问题是否能用动态规划来解决，也就看是否具有上面上所说的最优子结构和重复子问题是否蕴含在题目之中。先定义下相关约定：设数组A的每个元素为Ai(i=1..n)，目标target值为T，要求解的元素集合为X。

我们先看下能不能定义一个最优子结构。我一开是想到的是假设W(i)定义为从A取i个元素中某几个元素之和，使该和在前i个元素中最接近T。显然，我们的目标是找出W(n)-T=0的元素组合X。这时我们尝试找出父子问题的关系：W(j)=APPR {W(j-1)+Aj,W(j-1)} ，W(j)是前j个元素中能选出的最接近T的和，W(j-1)是j-1元素中能选出的最接近T的和，APPR{} 表示从大括号里面比较看哪个值更接近target值。该公式尝试定义这么一个关系：前j个元素中能构成最接近T的元素之和，等于2个子问题W(j-1)+Aj和W(j-1)中最接近T的那一个。但实际情况是，该等式是不成立的。因为当W(j-1)最接近T的时候，W(j-1)+Aj不一定最能最接近T,就是说，该候选解不具备最优子结构。只有当W(j-1)最接近T-Aj时候，W(j-1)+Aj才会存在最优。

所以我们应该把前i个元素中被选元素最接近某个值的和也加入到W的参数中。可以定义：W(s,j)的值为选取前i个元素中某几个元素的和，使该和与s最接近。这样，W(s,j)=APPR {W(s-Aj, j-1)+Aj,W(s,j-1)}。W(s-Aj, j-1)+Aj表明在选择Aj作为X的元素之一的情况下所能达到最接近s的值，W(s,j-1)表明在不选择Aj作为X的元素时所达到最接近s的值，二者最接近s的就作为W(s,j)的值。这样，当各个子问题求出最优解时，父问题就迎刃而解了。目标就是求W(T, j)时候X的组合。

找出最优子结构，并且给予递归定义后，我们就可以从下往上地进行计算了。从W的参数可以看出，构造保存计算结果的矩阵大小为s x j。

递归边界条件：（1）s>=1，j>=1;

（2）当j=1是，W(s, 1)=A1; （1）（2）推得：W(i, 1)=A1 (i=1..n)

（3）当s<Aj 时，W(s-Aj, j-1)= 0;

（4）当s=Aj 时，W(s,j)=s=Aj 。

迭代计算过程如下：

对每个j循环for(j=2..n)
对每个s循环for(s=1..Sum(A))
          if(s=Aj)W[s][j]=Aj并到下一个s
          if(s<Aj)
            set选择Aj的最接近和=Aj
          else
            set选择Aj的最接近和=W[s-Aj][j-1]+Aj;
          endif
          set不选择Aj的最接近和=W[s][j-1]
          if(选择Aj使得更接近s){
            setW[s][j]=不选择Aj的最接近和
          else
            setW[s][j]=选择Aj的最接近和
          endif
endfor
endfor

经过计算后W(T, j)就是最接近T的值，假如W(T, j)=T，那么此时的X就是所求元素的组合

结果有了，但是X的具体最优解元素时那几个数呢？这是，W矩阵已经填充了数值，只要再根据W(s,j)=APPR {W(s-Aj, j-1)+Aj,W(s,j-1)} ，即可在每次计算中判断是否选择第j个元素了。

具体实现代码在文章最后给出。

问题解决了，但是，这个父子关系的递归式只有这一个吗？为什么用s参数和j参数来限定子问题？类似的，我们还可以用下面这个递归式表示：

W(s, {M})=APPR {W(s-Ai, {M-Ai})+Ai : Ai属于{M})}

其中{M}表示一个若干Ai的集合。这个递归式定义W(s,{M})为从{M}中取若干个元素使其相加最接近s时的和。这个和原来的其实很像，但是区别在于，后者中每个拥有n个元素{M}的父问题都有n-1个子问题。这样递归到最底层就有n!个子问题需要解决。而本质上原问题假使用穷举的方法枚举所有可能性，也只有2的n次方个问题，说明第二种子结构的划分要解决大量重复的子问题。因为W(s, {M})中引入的集合具有无序性，而第一个W(s,j)却利用了有序性，由此可见不同的子结构在解决问题的范围还是有很大差异，关键是要提高子问题在甄别问题的解的效率。关于这个问题可以参考下面这篇文章：http://mindhacks.cn/2010/11/14/the-importance-of-knowing-why-part2/。其实文章所讨论的问题的解决思路也是借鉴于这篇文章的^_^。

附程序（该程序求解是回溯算法复习里面的题目，原理一样，本篇文章开头问题的代码就不另外贴出了）：

package puzzle;


/**
 * 给出一个数组，要怎么划分成2个数组使得2数组和之差最少<br/>
 * 本质上就是，从数组中如何取数使其和等于某个target值，这里分割后的2个数组的平均值就是target值
 * @author nizen
 *
 */
public class ArrayCutting {

	private int avg;
	
	private int[][] k;
	
	private void checkit(int[] array){
		if (array == null || array.length==0) {
			throw new IllegalArgumentException();
		}
	}
	// 初始化定义target值和边界值
	private void init(int[] array) {
		int sum = 0;
		for(int i=0;i<array.length;i++) {
			sum += array[i];
		}
		avg = Math.round(sum / 2);
		
		k = new int[avg+1][array.length+1];
		
		for (int w=1; w<=avg; w++) {
			for(int j=1; j<=array.length; j++) {
				if (j==1){
					k[w][j]=getValueJ(array,j);
					continue;
				}
			}
		}
	}
	
	public int[] cutit(int[] array) {
		checkit(array);
		
		init(array);
		
                // 自底向上构造矩阵
		for (int j=2; j<=array.length; j++) {
			for (int w=1; w<=avg; w++) {
				int valueAfterCutJ = w-getValueJ(array,j);
				int lastJ = j-1;
				
				if (valueAfterCutJ == 0) {
					k[w][j] = getValueJ(array,j);	//选择J后差值为0则选择J为结果值
					continue;
				}
				int valueChooseJ = 0;
				if (valueAfterCutJ < 0) {
					valueChooseJ = getValueJ(array, j); //期望值比J小则取J为选择J后的值
				} else {
					valueChooseJ = k[valueAfterCutJ][lastJ] + getValueJ(array,j);
				}
				
				if (Math.abs(k[w][lastJ]-w) < Math.abs(valueChooseJ-w)  ) {
					k[w][j]=k[w][lastJ];
				} else {
					k[w][j]=valueChooseJ;
				}
			}
		}
		
		return findPath(array);
	}
	
        // 最后一步：构造出最优解
	private int[] findPath(int[] array) {
		int[] result = new int[array.length];
		int p=0;
		int j=array.length;
		int w=avg;
		while(j>0){
			int valueAfterCutJ = w-getValueJ(array,j);
			int lastJ = j-1;
			
			if (valueAfterCutJ == 0) {	//清0跳出
				result[p++]=getValueJ(array,j);
				w=w-getValueJ(array,j);
				break;
			}
			int valueChooseJ = 0;
			if (valueAfterCutJ < 0) {
				valueChooseJ = getValueJ(array, j); //期望值比J小则取J为选择J后的值
			} else {
				valueChooseJ = k[valueAfterCutJ][lastJ] + getValueJ(array,j);
			}
			
			if (Math.abs(k[w][lastJ]-w) > Math.abs(valueChooseJ-w)  ) {
				result[p++]=getValueJ(array,j);
				w=w-getValueJ(array,j);
			}
			j=j-1;
		}
		return result;
	}

	public static void main(String[] args) {
		ArrayCutting ac = new ArrayCutting();
		int[] r = ac.cutit(new int[]{87,54,51,7,1,12,32,15,65,78});
		int selectedSum = 0;
		for (int i=0;i<r.length;i++){
			if (r[i]>0){
				selectedSum +=r[i];
				System.out.print(r[i]+"+");
			}
		}
		System.out.println("="+selectedSum+" Target="+ac.avg);
	}
	
        // 返回第j个数组元素
	private int getValueJ(int[]array, int j){
		return array[j-1];
	}
}