在M件物品取出若干件放在空间为W的背包里，每件物品的体积为W1，W2……Wn，与之相对应的价值为P1,P2……Pn。求出获得最大价值的方案。
注意：在本题中，所有的体积值均为整数。01的意思是，每个物品都是一个整体，要么整个都要，要么都不要。
1）最优子结构
考虑所有物品的子集合，考虑第n个物品都有两种情况: 1. 包括在最优方案中2. 不在最优方案中因此，能获得的最大价值，即为以下两个值中较大的那个
1) 在剩下 n-1 个物品中(剩余 W 重量可用)的情况能得到的最大价值 (即排除了 第n个物品)
2)第n个物品的价值 加上 剩下剩下的 n-1 个物品(剩余W- wn的重量)能得到的最大价值。(即包含了第n个物品)
如果第n个物品的重量，超过了当前的剩余重量W，那么只能选情况1)， 排除第n个物品。
【动态规划实例（七）（01背包问题最大价值）】2) 重叠子问题*/
具体实例及实现代码如下所示：
/** * @Title: ZeroOneKnapSack.java * @Package dynamicprogramming * @Description: TODO * @author peidong * @date 2017-6-8 上午8:54:18 * @version V1.0 */ package dynamicprogramming; /** * @ClassName: ZeroOneKnapSack * @Description: 0-1背包问题 * @date 2017-6-8 上午8:54:18 * */ public class ZeroOneKnapSack {/** * * @Title: knapSackRecursion * @Description: 递归求解0-1 规划问题, 返回前n个物品在容量为w，得到的最大价值 * @param w 背包总重量 * @param wt 物品重量数组 * @param vt 物品价值数组 * @param n 物品数量 * @return * @return int * @throws */ public static int knapSackRecursion(int w, int[] wt, int[] vt, int n){ //边界条件判断 if(n == 0 || w ==0) return 0; //d当前n个物品超重时 if(wt[n-1] > w) return knapSackRecursion(w, wt, vt, n-1); else return Math.max(vt[n-1] + knapSackRecursion(w-wt[n-1], wt, vt, n-1), knapSackRecursion(w, wt, vt, n-1)); //返回如下两种情况较大值（1）包含第n个物品（2）不包含第n个物品 }public static int knapSack(int w, int[] wt, int[] vt, int n){ //创建状态转移矩阵 int[][] tc = new int[n+1][w+1] ; //构建状态转移矩阵 for(int i = 0; i<= n; i++){ for(int j = 0; j <= w; j++){ //边界条件 if(i == 0 || j == 0){ tc[i][j] = 0; }else if(wt[i-1] <= j) tc[i][j] = Math.max(vt[i-1] + tc[i-1][j-wt[i-1]], tc[i-1][j]); else tc[i][j] = tc[i-1][j]; } } return tc[n][w]; } /** * @Title: main * @Description: TODO * @param args * @return void * @throws */ public static void main(String[] args) { // TODO Auto-generated method stub int[] vt = {1, 1, 2, 2, 3, 3, 4, 5}; int[] wt = {8, 10, 13, 15, 20, 24, 28, 33}; int w = 12; int n = vt.length; System.out.println("利用递归求解01背包问题最大价值为：" + knapSackRecursion(w, wt, vt, n)); System.out.println("利用动态规划求解01背包问题最大价值为：" + knapSack(w, wt, vt, n)); }}
