目录
1、0-1背包
1.1、动态迁移方程
1.2、优优化空间复杂度
1.3、回溯算法解决
1.2、相关习题
2、完全背包
2.1、动态迁移方程
2.2、转换成0-1背包
2.3、优化空间复杂度
2.4、相关习题
3、小结
给你一个可装载重量为 W 的背包和 N 个物品，每个物品有重量和价值两个属性。其中第 i 个物品的重量为 wt[i]，价值为 val[i]，现在让你用这个背包装物品，最多能装的价值是多少？
N = 3, W = 4 wt = [2, 1, 3] val = [4, 2, 3]
算法返回 6，选择前两件物品装进背包，总重量 3 小于 W，可以获得最大价值 6
每种物品仅有一件，可以选择放或不放。用子问题定义状态：dp[i][j] 表示前 i 件物品恰放入一个容量为 j 的背包可以获得的最大价值。则其状态转移方程如下：
dp[i][j] = max(dp[i-1][j], dp[i-1][j-wt[i-1]]+val[i-1]);注意：物品数组的起始位置，wt[ i-1],val[i-1]表示第 i 件物品的重量和价值。这个方程非常重要，基本上所有跟背包相关的问题的方程都是由它衍生出来的。所以有必要将它详细解释一下：“将前 i 件物品放入容量为 j 的背包中” 这个子问题，若只考虑第 i 件物品的策略（放或不放），那么就可以转化为一个只牵扯前 i−1 件物品的问题。① 如果不放：第 i 件物品，那么问题就转化为“前 i−1件物品放入容量为 j 的背包中”，此时价值为 dp[ i ][ j ] = dp[ i-1 ][ j ]；②如果放：第 i 件物品，那么问题就转化为“ 前 i−1 件物品放入剩下的容量为 j−wt[i-1] 的背包中”，此时能获得的最大价值就是 dp[ i-1 ][ j-wt[i-1] ] 再加上通过放入第 i 件物品获得的价值val[i]，即dp[i][j] = dp[ i-1 ][ j-wt[i-1] ] + val[i-1]。
public int maxValEx(int[] wt,int[]val,int w){ int [][]dp = new int[wt.length+1][w+1]; for(int i = 1; i <= wt.length; i++){ for(int j = 0; j <= w; j++){ if(j >= wt[i-1]){ dp[i][j] = Math.max(dp[i-1][j],dp[i-1][j - wt[i-1]]+val[i-1]); }else{ dp[i][j]=dp[i-1][j]; } } } return dp[wt.length][w]; }时间复杂度：O（N*W），空间复杂度：O（N*W）
以上方法的时间和空间复杂度均为O(N*W)，其中时间复杂度已经不能再优化了，但空间复杂度却可以优化到O(W)。上文二维数组实现算法：主循环 i = 1...N，每次算出来二维数组 dp[i][0...W] 的所有值。那么，如果只用一个数组dp[0...V]能不能保证第 i次循环结束后dp[j]中表示的就是我们定义的状态dp[i][j]呢？dp[i][j] 是由 dp[i-1][j] 和 dp[i-1][j - wt[i-1]]+val[i-1] 两个子问题递推而来，能否保证在推 dp[i][j] 时（也即在第i次主循环中推dp[j]时）能够得到dp[i-1][j] 和dp[i-1][j - wt[i-1]]的值呢？事实上，这要求在每次主循环中我们以 j = W...0的顺序推导dp[j]，这样才能保证推 dp[j] 时 [j - wt[i-1]] 保存的是状态dp[i-1][j - wt[i-1]]的值。代码如下：
public int maxValExx(int[] wt,int[]vt,int k){ int []dp = new int[k+1]; for(int i = 1; i <= wt.length; i++){ for(int j = k ; j >=0; j--){ if(j >= wt[i-1]){ dp[j] = Math.max(dp[j],dp[j - wt[i-1]]+vt[i-1]); } } } return dp[k]; }此时的 dp[j] = Math.max(dp[j],dp[j - wt[i-1]]+vt[i-1]) 相当于 dp[i][j] = max(dp[i-1][j], dp[i-1][j-wt[i-1]]+val[i-1])，因为我们是降序遍历包重 计算dp[j] 时 dp[ j - wt[i-1] ] 保存的是上一轮循环的值，如果依然保持升序遍历包重，计算dp[j] 时 dp[ j - wt[i-1] ]已经被本轮循环先计算更新过，此时dp[i][j]依赖的是 dp[ i ][ j - wt[i-1] ]，而不在是dp[ i-1 ][ j - wt[i-1] ]。此时状态迁移方程表示的是完全背包而非0-1背包。
继续优化减少迭代次数
.... for(int j = k ; j >= wt[i-1]; j--){ dp[j] = Math.max(dp[j],dp[j - wt[i-1]]+vt[i-1]); } ....算法： 1、新建一个物品类存储物品重量和价值 2、从物品列表 list 中依次选取物品 i 进包，做出选择，在选择列表中置为物品i为无效值，递归计算，物品进包，包重减少，商品总值增加。 3、依次选取下一件物品，直至选择列表为空，或者包中已经放不下任何一件物品，返回价值为0 4、撤销选择，物品i恢复到选择列表 5、更新本分支下包中物品的总价值
public int maxValue(int []wts,int []vals, int W) { if(wts.length != vals.length || W <= 0) { return 0; } List<Goods> list = new ArrayList<Goods>(); for(int i = 0;i < wts.length; i++) { list.add(new Goods(wts[i], vals[i])); } return maxValue(list,W); } public int maxValue(List<Goods> list, int W) { if(list == null) { return 0; } int maxValue = 0; for(int i = 0; i < list.size(); i++) { //1、物品已被选；2、物品超重 if(list.get(i) == null || W < list.get(i).getWeight()) { continue; } Goods goods = list.get(i); list.set(i,null);//做出选择置为无效 //放入包中 int Val = maxValue(list,W-goods.getWeight()) + goods.getValue(); list.set(i,goods);//撤销选择，恢复物品 maxValue = Math.max(maxValue, Val);//更新最大值 } return maxValue; } class Goods{ int weight; int value; public int getWeight() { return weight; } public int getValue() { return value; } public Goods(int weight, int value) { super(); this.weight = weight; this.value = value; } }核心代码：
.... for(int i = 0; i < list.size(); i++) { //1、物品已被选；2、物品超重 if(list.get(i) == null || W < list.get(i).getWeight()) { continue; } Goods goods = list.get(i); list.set(i,null);//做出选择置为无效 //放入包中 int Val = maxValue(list,W-goods.getWeight()) + goods.getValue(); list.set(i,goods);//撤销选择，恢复物品 maxValue = Math.max(maxValue, Val);//更新最大值 } ...《0-1背包相关题集》
和 0-1背包唯一的的区别就是，每个物品的数量是无限的，也就是从每种物品的角度考虑，与它相关的策略已并非取或不取两种，而是有取 0 件、取 1 件、取 2件……直至取 [ W/wt[i] ] 件等许多种。在前 i - 1种物品的包中，列举出添加0,1... j/wt[i-1]件物品 i 的所有场景，取最大值，状态迁移方程如下：
dp[i][j] = max(dp[i-1][ j- k*wt[i-1] ]+k*val[i-1]) (0<= k <= j/wt[i-1]);代码如下：
public int maxVal(int[] wt,int[]val,int w){ int [][]dp = new int[wt.length+1][w+1]; for(int i = 1; i <= wt.length; i++){ for(int j = 0; j <= w; j++){ int max =0; for(int k=0;k <=j/wt[i-1]; k++) { max = Math.max(max,dp[i-1][j - k*wt[i-1]]+k*val[i-1]); } dp[i][j]=max; } } return dp[wt.length][w]; }第 i 件物品从0，1,,, j/wt[i-1] 件依次放入，k件物品 i 的放入取决于 k-1件物品 i 的放入。
上文可知max变量为每次放入1件物品 i 最大价值，因此 dp[i][j] 是依赖上一件物品 i 放入dp[i][j]，替换max变量如下：
.... for(int k=0;k <=j/wt[i-1]; k++) { dp[i][j] = Math.max(dp[i][j],dp[i-1][j - k*wt[i-1]]+k*val[i-1]); } ...此时状态迁移方程为：
dp[i][j] = max(dp[i-1][j],dp[i][j-wt[i-1]]+val[i-1]);和0-1不同是当物品 i 放入时 dp[i][j] 依赖的 dp[i][j-wt[i-1]]，而不是dp[i-1][j-wt[i-1]]， 因为，0-1背包必须保证一件物品只能放一次，当执行物品i放入时，必须保证包中没有物品 i，因此只能从 i-1 件物品中推导；而完全背包则不同，每件物品 i 可以添加无限次，因此，当物品 i 放入时，需要考虑在物品 i 已经在包中的场景即 dp[i][j-wt[i-1]]。
public int maxVal(int[] wt,int[]val,int w){ int [][]dp = new int[wt.length+1][w+1]; for(int i = 1; i <= wt.length; i++){ for(int j = 0; j <= w; j++){ if(j>=wt[i-1]) { dp[i][j] = Math.max(dp[i-1][j],dp[i][j -wt[i-1]]+val[i-1]); }else { dp[i][j] = dp[i-1][j]; } } } return dp[wt.length][w]; }