算法设计方法4：动态规划经典例题总结( 二 ) _动态规划

4、边界情况分析
跳一阶时，只有一种跳法，所以f(1)=1
跳两阶时，有两种跳法，直接跳2阶，两次每次跳1阶，所以f(2)=2

文章插图
跳两阶以上可以分解成上面的情况
Java代码：

public static int jump(int n) { //无意义的情况 if(n <= 0) return 0; if(n == 1) return 1; if(n == 2)return 2; //数组用于存储跳n阶的跳法数 int[] value = http://www.kingceram.com/post/new int[n + 1]; value[0] = 0; value[1] = 1;value[2] = 2;for(int i = 3; i <= n; i++) { value[i] = value[i - 1] + value[i - 2]; }return value[n]; }

三、01背包问题
问题描述：有n个物品(每种物品仅有一件)，每种物品i都有自己的重量Wi和价值Vi 。现有给定容量为M的背包，我们应该如何选择物品装入背包，使得装入背包的物品总价值最大？
假定每件物品i的装入情况为Xi,得到的效益是Vi*Xi 。
(1)部分背包问题：在选择物品时，可以将物品分割为部分装入背包，即0≤x≤1 (贪心算法) 。
(2) 0/ 1背包问题：和部分背包问题相似，但是在选择物品装入时要么不装，要么全装入，即x=1或0 。(动态规划算法) 。
01背包问题分析：设我们的背包里面的物品价值为b，给背包添加两个参数：k和c，即b(k,c),那么b(k,c)又表示什么什么意思呢？
k表示你面对的物品编号，即1~5,
c表示你面对k号物品时，背包的剩余容量
b(k,c)表示面对k号物品，并作出拿或不拿的选择之后，背包里面的物品总价值
举个例子，b(2,20)表示的是，在你的背包容量为20的情况下，当你面对2号物品时并作出拿或者不拿的选择后，背包中物品的总价值。
了解了这个概念后我们继续：
假设你现在遇见了第k号物品，此时你的背包容量为c，你得做出一个决策，到底要不要拿走第k件物品呢？那么拿不拿的前提是啥？当然是这个物品重不重，能不能塞到包里。
第一种情况：
如果第k件物品的重量w[k]比此时的背包的剩余重量c大了，那我肯定是拿不动了，即w[k]>c 。所以此时包中物品的价值就是我拿的前一个物品之后包中的价值，即 b(k,c)=b(k-1,c).包中剩余空间不变，还是c 。
第二种情况：
如果我拿得动第k件物品，即第k件物品的重量w[k]，面对k号物品，无外乎两种选择，拿或者不拿，这时我就要根据拿走之后产生的效益进行决策了：
不拿k号物品，那么此时包中物品的总价值b(k,c)=b(k-1,c)，和第一种拿不动k号物品的一样。
拿走k号物品，那么此时包中物品的总价值b(k,c)=b(k-1,c-w[k])+v[k]拿了第k件物品后，那我的包中的价值肯定就是原先的价值再加上第k件物品的价值(动态规划)，而且拿了之后包中的剩余容量就为c-w[k]了。总结一下，就是如下的公式了：b(k,c)=max{b(k-1,c),b(k-1,c-w[k])+v[k]}，即剩下的只需要比较这两种方式谁的效益大即可。
思维导图如下：
Java代码：

class Main{public static void main(String[] args) {int[] w = { 0, 2, 3, 4, 5, 9 };//每种物品的重量int[] v = {0, 3, 4, 5, 8, 10 };//每种物品的价值int N = 6,int capacity = 21;//背包容量int[][] b = new int[N][capacity];for (int k = 1; k < N; k++) {for (int c = 1; c  c) {b[k][c] = b[k - 1][c];}else {int value1 = b[k - 1][c - w[k]] + v[k]; // 拿第k件物品int value2 = b[k - 1][c]; // 不拿第k件物品b[k][c] = Math.max(value1, value2);}}}System.out.println(b[5][21]);//输出26}}

最优解即是b(n,)，但是我们并不清楚具体选择哪几样物品能获得最大价值。
另起一个 x[ ] 数组，x[i]=0表示不拿，x[i]=1表示拿。