动态规划（一）之背包问题

如果一个问题可以用动态规划来解决，那么这个问题需要满足两个条件：

1）这个问题可以分解成很多子问题，并且这些子问题的最优解给合起来，就是大问题的最优解。

2）这些很多的子问题有很多是重复的。

下面是经典的背包问题：

	private static int N = 8;
	private static int[] weights = {1,3,5,3,2,2,4,5};
	private static int[] values = {10,30,40,33,20,17,35,36};

有8个物体，它们的重量和价值分别是weights里面的值和values里面的值，那么我们可以根据重量来分别列出当重量为1的时候，为2的时候，以此类推：

weight = 1
0	1	2	3	4	5	6	7	8	9	10	11	
0	10	0	0	0	0	0	0	0	0	0	0	
0	10	0	0	0	0	0	0	0	0	0	0	
0	10	0	0	0	0	0	0	0	0	0	0	
0	10	0	0	0	0	0	0	0	0	0	0	
0	10	0	0	0	0	0	0	0	0	0	0	
0	10	0	0	0	0	0	0	0	0	0	0	
0	10	0	0	0	0	0	0	0	0	0	0	
0	10	0	0	0	0	0	0	0	0	0	0

当背包的weight = 1 的时候，依次将8个物品往里面放，我们发现只有第1件物品能放进去，其它的都超重了，所以对于weight = 1来说，其最优解就是10。

weight = 2
0	1	2	3	4	5	6	7	8	9	10	11		
0	10	10	0	0	0	0	0	0	0	0	0	
0	10	10	0	0	0	0	0	0	0	0	0	
0	10	10	0	0	0	0	0	0	0	0	0	
0	10	10	0	0	0	0	0	0	0	0	0	
0	10	20	0	0	0	0	0	0	0	0	0	
0	10	20	0	0	0	0	0	0	0	0	0	
0	10	20	0	0	0	0	0	0	0	0	0	
0	10	20	0	0	0	0	0	0	0	0	0

当背包的weight = 2 的时候，依次将8个物体往背包里放，我们可以发现，

1）第1件物品是可以放进去的，此时，背包的价值是10。

2）第2，3，4都不能放进去，所以到第4件物品的时候，其最优解还是10。

3）但是第5件物品，它的重量刚好是2，这个时候，它是可以放进包里的，只要将第一件物品拿出来就好了，而其价值是20，比第1件物品要高，所以我们将其放进去，将第1件物品拿出来，此时最优解是20。

4）第6件物品还是2，但是其价值只有17，相比20，还是不够最优，所以不理它。

5）接下来的7，8也是超重了。

所以当背包的weight = 2来说，其最优解是20。

weight = 3
0	1	2	3	4	5	6	7	8	9	10	11	
0	10	10	10	0	0	0	0	0	0	0	0	
0	10	10	30	0	0	0	0	0	0	0	0	
0	10	10	30	0	0	0	0	0	0	0	0	
0	10	10	33	0	0	0	0	0	0	0	0	
0	10	20	33	0	0	0	0	0	0	0	0	
0	10	20	33	0	0	0	0	0	0	0	0	
0	10	20	33	0	0	0	0	0	0	0	0	
0	10	20	33	0	0	0	0	0	0	0	0

当背包的weight = 3的时候，类似于上面的做法：

1）第1件物品是可以放进去的，此时，背包的价值是10。

2）第2件物品重量刚好是3，且其价值比10大，所以将这个放进背包，将原来第1件拿出去，此时最优解是30。

3）第3件物品重量是5，pass掉，所以此时最优解还是30。

4）第4件物品重量也是3，而且其价值是33，将这件放进去，将第2件拿出来，此时最优解是33。

5）第5件物品的重量是2，是可以放进包里的，如果将其放进包里，其价值是20，那么还有剩下重量1，所以我们要找出在还没放当前这一个物品，且重量为1时候的最优解，那就是weight = 1的时候（第1列，上面的表从第0列开始），只有4件物品时候的最优解，很显然就是10，两个加起来才30，显然还不如只放第4件物品的时候，所以还是只放第4件物品，最优解还是33。

6）第6件物品跟第5件一样的方法，可以放，但是不够最优，第7，第8都超重了，所以不理。

所以当背包的weight = 3的时候，其最优解是33。

weight = 4
0	1	2	3	4	5	6	7	8	9	10	11	
0	0	0	0	0	0	0	0	0	0	0	0	
0	10	10	10	10	0	0	0	0	0	0	0	
0	10	10	30	40	0	0	0	0	0	0	0	
0	10	10	30	40	0	0	0	0	0	0	0	
0	10	10	33	43	0	0	0	0	0	0	0	
0	10	20	33	43	0	0	0	0	0	0	0	
0	10	20	33	43	0	0	0	0	0	0	0	
0	10	20	33	43	0	0	0	0	0	0	0	
0	10	20	33	43	0	0	0	0	0	0	0

当背包的weight = 4来说，

1）第1件物品是可以放进去的，此时，背包的价值是10。

2）第2件物品重量是3，可以放进包里，其价值是30，还有剩下重量是1，很显然，我们也可以发现在放此物品前，重量为1时的最优解就是放前面第1件物品的时候，所以两件加起来，重量刚好是4，总价值是40，是此时的最优解。

3）第3件物品重量是5，超重，不理，最优解还是40。

4）第4件物品重是是3，可以放进包里，其价值是33，还有剩下重量是1，很显然，我们也可以发现在放此物品前，重量为1时的最优解就是放前面第1件物品的时候，所以两件加起来，重量刚好是4，总价值是43，与前一个的最优解相比要大，所以此时的最优解应该是放进第4件和第1件物品，价值是43。

5）第5件物品重量是2，可以放得进去，其价值是20，剩下重量是2，而我们发现当减去重量2，在前面4件物品中，最优解是10（第2列，第5行，全是0那行是第一行），那么总的价值才30，显然不如43，所以最优解还是43。

其它的类推，所以最后发现8件物品都选完，解出当weight = 4的时候，最优解就是43。

根据上面这样的逻辑，我们可以分别求出当背包的总重是多少的时候，最优解是什么，还可以求出选择了哪些物品。

weight = 11
0	1	2	3	4	5	6	7	8	9	10	11	
0	0	0	0	0	0	0	0	0	0	0	0	
0	10	10	10	10	10	10	10	10	10	10	10	
0	10	10	30	40	40	40	40	40	40	40	40	
0	10	10	30	40	40	50	50	70	80	80	80	
0	10	10	33	43	43	63	73	73	83	83	103	
0	10	20	33	43	53	63	73	83	93	93	103	
0	10	20	33	43	53	63	73	83	93	100	110	
0	10	20	33	43	53	63	73	83	93	100	110	
0	10	20	33	43	53	63	73	83	93	100	110

上面是当weight = 11的时候，求出的最优解。

由上面这样一个表格我们也可以看出，

1）求weight = 11的时候，我们可以将它分解成求很多个小weight的问题，分别是weight = 1，2，。。。的问题。

2）当求weight = 11的时候，我们会利用到之前算出来的weight = 1，2，。。。的解，而且因为我们将之前的解已经存了起来，我们就不需要再计算，直接拿来用就行。

这就是动态规划的效率之所以比较高的原因了，因为我们节省了重复计算的时间的。

接下来将整个代码贴上来，大家对比着看一下吧。

package com.lms;

public class Knapsack {

	private static int N = 8;
	private static int[] weights = {1,3,5,3,2,2,4,5};
	private static int[] values = {10,30,40,33,20,17,35,36};
	
	private static int totalWeight = 11;
	
	public static void main(String[] args){
		int[][] results = new int[N+1][totalWeight + 1];
		
		for(int i=0;i<=N;i++){
			for(int j=0;j<=totalWeight;j++){
				results[i][j]=0;
			}
		}
		
		for(int j=1;j<=totalWeight;j++){
			for(int i=1;i<=N;i++){
				if(weights[i-1] > j){
					results[i][j] = results[i-1][j];
				}else{
					results[i][j] = max(results[i-1][j], results[i-1][j-weights[i-1]] + values[i-1]);
				}
			}
			System.out.println("weight = " + j);
			print(results);
		}
		System.out.println(results[N][totalWeight]);
	}
	
	private static void print(int[][] results){		
		
		for(int j=0;j<=totalWeight;j++){
			System.out.print(j + "\t");
		}
		System.out.println();
		for(int i=0;i<=N;i++){
			for(int j=0;j<=totalWeight;j++){
				System.out.print(results[i][j] + "\t");;
			}
			System.out.println();
		}
		
	}
	
	private static int max(int a, int b){
		return a > b ? a : b;
	}
}

而此算法的重点就是下面这两句：

if(weights[i-1] > j){
    results[i][j] = results[i-1][j];
}else{
    results[i][j] = max(results[i-1][j], results[i-1][j-weights[i-1]] + values[i-1]);
}

第一个是判断

1）当前物品的重量是不是比这个背包重，如果比这个背包重，我们就直接pass，就是我们上面举例说的第三步了，背包重量只有1的时候，重量大于1的都不用考虑。

第二个是判断：

2）当物品的重量是可以放进背包的时候，就要考虑一下，放了这个物品之后，剩下的重量的最优解加上当前物品的价值是不是比放上一个物品的最优解更“优”，取较优的那个解。