问题：

有 N 件物品和一个容量为 V 的背包。放入第 i 件物品耗费的空间是 Ci ,得到
的价值是 W i 。求解将哪些物品装入背包可使价值总和最大。

解题思路：

其实一开始看这题，会让人有些不知所措，不过，这题是有规律可寻的。此题的特点是:每种物品仅有一件,可以选择放或不放。
用子问题定义状态:即 F [i, v] 表示前 i 件物品恰放入一个容量为 v 的背包可以获得的最大价值。则其状态转移方程便是

F [i, v] = max {F [i − 1, v], F [i − 1, v − Ci ] + Wi }

对这个方程的解释如下： 将前 i 件物品放入容量为 v 的背包中”这个子问题,若只考虑第 i 件物品的策略(放或不放),那么就可以转化为一个只和前 i − 1 件物品相关的问题。如果不放第 i 件物品,那么问题就转化为“前 i − 1 件物品放入容量为 v 的背包中”,价值为 F [i − 1, v] ;如果放第 i 件物品,那么问题就转化为“前 i − 1 件物品放入剩下的容量为 v − Ci 的背包中”,此时能获得的最大价值就是 F [i − 1, v − Ci ] 再加上通过放入第 i 件物品获得的价值 Wi 。 从网上的图解

基于这个方程就可以写出程序了，代码如下：

public int getMaxValue(int[] w, int[] v, int weight){
        //n为商品的数量  
        int n = w.length;
        int[][] value = new int[n+1][weight+1];
        for(int i = 1;i<=n;i++){
            for(int j = 1;j<=weight;j++){
                 /*当物品为i件重量为j时，如果第i件的重量(w[i-1])小于重量j时，c[i][j]为下列两种情况之一：
                1.物品i不放入背包中，所以c[i][j]为c[i-1][j]的值
                2.物品i放入背包中，则背包剩余重量为j-w[i-1],所以c[i][j]为c[i-1][j-w[i-1]]的值加上当前物品i的价值*/
                if(w[i-1]<=j){
                    value[i][j]=Math.max(value[i-1][j], value[i-1][j-w[i-1]]+v[i-1]);
                }
            }
        }
        return value[n][weight];
}

//测试数据
/*
 *     int weight = 10;
 *     int[] w = {3,4,5};
 *     int[] p = {4,5,6};
*/