动态规划算法

其实我一直在想一个问题，为什么我觉得学习计算机算法比高中的数学难？

 

记得高中的数学那是信手撵来（当然不是每一道题目），不谈学得有多好，但是起码对待每一道数学题都有自己的思路，想法，一般都能解出来，但是为什么学习计算机算法的时候就没有这种感觉呢。宏观上看过去第一眼肯定是计算机算法一般都是文字性表述，应该比高中的数学逻辑简单吧。但是，为什么学习计算机算法就感觉特别不自然。对于简单的题目套用简单的解法思路都好难实现出来，难道是我的脑袋退化了？

 

不过，客观上讲，大学课程，当然要比高中课程层次要高。

 

由于我看的是算法导论，所以讲的比较清楚（PS：翻译不说有多好，但是肯定会有晦涩的地方），关于高级的计算机算法设计中分为3类问题（按照书上划分的）：动态规划，贪心算法，平摊分析。其实，计算机算法也有运筹学的内容，有关效率选择，最大价值等等。我能想到的应用就是什么主从节点的选择，考虑到最少的成本而获得最大计算机利用率之类的。我自然时根据书中的规划来学习的，首先接触的是动态规划。

 

在现实问题中，人们对于这样一类问题：在进行解的选择时，下一步的选择会影响到前面的选择而导致整个前面选择的解发生变化，这样，人们的脑袋可是想象不过来，递归的进行重新选择解（如果人的脑袋有很好的rom就好了）；其实在没有接触贪心算法的时候，我们很擅长用这种思想解决问题，比如进行路程最短问题，我们总是会先选择我们能进行选择的路程试探，找到最短的路程，然后在进行下一步的选择，这是最简单的思想，所谓贪心算法。但是，就像我方才提到的，有些问题是不能通过“贪心”选择的，下面是一个方便的例子（书上太多例子了，不知道那一个最能说明问题）：0-1背包问题；

 

小偷进入了一家首饰店，首饰店中每一件物品有且只有一件，共有n件，店中有太多的首饰，小偷看看他可怜的布袋，最多能装下体积为V的首饰，对于每一件首饰i，其价值为Wi，体积为Vi，所以，小偷要进行选择，选择在其布袋中能装下并且价值最大的一些首饰。（脚趾头想一想都知道，不能先选择价值最大的首饰，你们懂的～），貌似用高中排列组合的话，能取到是2的N次方种组合，而且还要考虑到体积最大问题，如果这个小偷有这种脑袋的话，他也算NB了（如果有，应该不用做小偷了），指数级的选择次数，计算机算法中它是低效的，那，我们现在来观察一下，有没有更好的办法。递归，貌似是很适合该类问题的，对于递归的解法，我们是要找到递归子，即对于每一个大问题，总有一个小问题能嵌于其中并且是递归嵌套的，0-1背包问题中，我们观察到，如果是在选择物品i时，其总价值最大并且体积不能超出，要么是在现在加入i物品后体积内除去该物品的最大价值，要么是在加入该物品后体积内包含该物品并且剩余体积内价值最大的物品组合。这是一个很难表述的解法，下面是一个函数式（其实时wiki上down的，有了它，好理解多了）：

f[i][j]{   
        f[i-1,j] {j<Vi}
        max{f[i-1,j],f[i-1,j-Vi]+Pi} {j>=Vi}
        0 {i=0 OR j=0}
}

关键是中间一个式子，我们来看一个具体的例子：

体积分别为：{2,2,6,5,4}
价值分别为：{6,3,5,4,6}

 现在，如果我们规定最大体积为6，我们直观看到如果我们选择第1，2件物品，体积为4，价值为9，如果我们继续添加，那么就超出了最大体积，现在，只能是在剩余的物品中替换现有的，首先考虑物品3，4，如果替换任意其中之一，那么将超出最大体积约束，再来看看物品5，体积为4，替换已有选择的物品中任意一件，不会破坏条件，那么，我们就来比较一下，如果替换了该物品，体积编程6，价值为12，大于9，但是，我们知道，现在体积变大了（原先是4），所以，我们还需要考虑在没有添加物品5之前，体积为6，并且最大价值最大的组合，貌似还是物品1，2的组合，价值为9，不大于现有价值12，那么，我们就可以成功添加该物品5。

 

下面是实现代码：

public class Bag_01{
	static void bag_pro(int[] w,int v[],int maxWeight){
		int[][] vw = new int[w.length][maxWeight+1];
		for(int i=0;i<maxWeight+1;i++){
			if(w[0]<=i){
				vw[0][i] = v[0];
			} else {
				vw[0][i] = 0;
			}
		}
		
		for(int i = 1;i<w.length;i++){
			for(int j = 0;j<maxWeight+1;j++){
				if(j<w[i]){
					vw[i][j] = vw[i-1][j];
				} else if(vw[i-1][j]<=(vw[i-1][j-w[i]]+v[i])){
					vw[i][j] = vw[i-1][j-w[i]]+v[i];
				} else {
					vw[i][j] = vw[i-1][j];
				}
			}
		}
		
		for(int i = 0;i<w.length;i++){
			for(int j = 0;j<maxWeight+1;j++){
				System.out.print(vw[i][j]+" ");
			}
			System.out.print("\n");
		}
	}

	public static void main(String args[]){
		int w[] = {2,2,6,5,4};
        	int v[] = {6,3,5,4,6};
        	int maxWeight = 6;
        	bag_pro(w,v,maxWeight);
	}
}

打印出来的是对每一规定最大体积内的体积逐步添加物品的最大价值的表；

 

上面的例子比较直观，用于动态规划的思路去解决问题，其思想就是找到一个可以递归的子问题，子问题的最优解即问题的最优解。这是我们思考问题的方式，递归使用于动态规划的寻找最优子问题结构，至于寻找子问题的解的结构，可以是迭代，也可以是递归。下面是“官方”步骤：

1.描述最优解结构；

2.递归定义最优解的值；

3.按自底向上的方式计算最优解的值；

4.由计算出的结果构造一个最优解；

当然，动态规划的最重要一点就是3，一定是自底向上求解过程，这样，才能运用到递归的子结构。通过子问题的最优解，得到问题的最优解。就像是背包问题，我们一定是求表中最后一列，最后一行的值，而该值是通过它的前列或者时前行得到的。

 

动态规划除了最优的子结构，还有一特征就是重叠的子问题，之所以动态规划能够缩减运行的时间，就是通过在以得到的子问题解中寻找值，而不是又一次计算，人脑之所以不能动态规划解决问题就是因为人脑没有那么一块地方保存先前计算的值，就算你记住了10个值，能记住100个？1000个？

 

最后，两点，重叠子问题，最优子结构，自底向上。