0-1背包问题

给定彻底理解0-1背包问题 - 图1个重量为彻底理解0-1背包问题 - 图2，彻底理解0-1背包问题 - 图3，彻底理解0-1背包问题 - 图4，…，彻底理解0-1背包问题 - 图5，价值为彻底理解0-1背包问题 - 图6，彻底理解0-1背包问题 - 图7，彻底理解0-1背包问题 - 图8，…，彻底理解0-1背包问题 - 图9的物品和容量为彻底理解0-1背包问题 - 图10的背包，求这些物品中一个最有价值的子集，使得在满足背包的容量的前提下，包内的物品总价值最大

注：0-1背包问题指的是每个物品只能使用一次

V1.0——递归方法

首先我们用最容易理解的递归方法来尝试解决这个问题

我们用彻底理解0-1背包问题 - 图11#card=math&code=F%28n%2CC%29&id=So5Pn)表示将前彻底理解0-1背包问题 - 图12个物品放进容量为彻底理解0-1背包问题 - 图13的背包里，得到的最大的价值。

我们从自顶向下的角度来看，假如我们已经进行到了最后一步（即求解将第彻底理解0-1背包问题 - 图14个物品放到背包所获得的最大价值），此时我们便有两种选择

  1. 不放第彻底理解0-1背包问题 - 图15个物品，此时总价值为彻底理解0-1背包问题 - 图16#card=math&code=F%28n-1%2CC%29&id=x1719)
  2. 放置第彻底理解0-1背包问题 - 图17个物品，此时总价值为彻底理解0-1背包问题 - 图18#card=math&code=v_n%2BF%28n-1%2CC-w_n%29&id=UErfZ)

两种选择中总价值最大的方案就是我们的最终方案，递推式（有时也称之为状态转移方程）如下

彻底理解0-1背包问题 - 图19%3Dmax(F(i-1%2CC)%2Cv(i)%2BF(i-1%2CC-w(i)))%0A#card=math&code=F%28i%2CC%29%3Dmax%28F%28i-1%2CC%29%2Cv%28i%29%2BF%28i-1%2CC-w%28i%29%29%29%0A&id=lUHAa)

编程实现如下：

  1. public class KnapSackV1 {
  2.     /**
  3.      * 解决背包问题的递归函数
  4.      *
  5.      * @param w        物品的重量数组
  6.      * @param v        物品的价值数组
  7.      * @param index    当前待选择的物品索引
  8.      * @param capacity 当前背包有效容量
  9.      * @return 最大价值
  10.      */
  11.     private static int solveKS(int[] w, int[] v, int index, int capacity) {
  13.         //基准条件：如果索引无效或者容量不足，直接返回当前价值0
  14.         if (index < 0 || capacity <= 0)
  15.             return 0;
  17.         //不放第index个物品所得价值
  18.         int res = solveKS(w, v, index - 1, capacity);
  20.         //放第index个物品所得价值（前提是：第index个物品可以放得下）
  21.         if (w[index] <= capacity) {
  22.             res = Math.max(res, v[index] + solveKS(w, v, index - 1, capacity - w[index]));
  23.         }
  24.         return res;
  25.     }
  27.     public static int knapSack(int[] w, int[] v, int C) {
  28.         int size = w.length;
  29.         return solveKS(w, v, size - 1, C);
  30.     }
  32.     public static void main(String[] args){
  33.         int[] w = {2,1,3,2};
  34.         int[] v = {12,10,20,15};
  35.         System.out.println(knapSack(w,v,5));
  36.     }
  37. }

V2.0——记忆化搜索

我们用递归方法可以很简单的实现以上代码，但是有个严重的问题就是，直接采用自顶向下的递归算法会导致要不止一次的解决公共子问题，因此效率是相当低下的。

我们可以将已经求得的子问题的结果保存下来，这样对子问题只会求解一次，这便是记忆化搜索。

下面在上述代码的基础上加上记忆化搜索

  1. public class KnapSack01 {
  3.     private static int[][] memo;
  5.     /**
  6.      * 解决背包问题的递归函数
  7.      *
  8.      * @param w        物品的重量数组
  9.      * @param v        物品的价值数组
  10.      * @param index    当前待选择的物品索引
  11.      * @param capacity 当前背包有效容量
  12.      * @return 最大价值
  13.      */
  14.     private static int solveKS(int[] w, int[] v, int index, int capacity) {
  15.         //基准条件：如果索引无效或者容量不足，直接返回当前价值0
  16.         if (index < 0 || capacity <= 0)
  17.             return 0;
  19.         //如果此子问题已经求解过，则直接返回上次求解的结果
  20.         if (memo[index][capacity] != 0) {
  21.             return memo[index][capacity];
  22.         }
  24.         //不放第index个物品所得价值
  25.         int res = solveKS(w, v, index - 1, capacity);
  27.         //放第index个物品所得价值（前提是：第index个物品可以放得下）
  28.         if (w[index] <= capacity) {
  29.             res = Math.max(res, v[index] + solveKS(w, v, index - 1, capacity - w[index]));
  30.         }
  32.         //添加子问题的解，便于下次直接使用
  33.         memo[index][capacity] = res;
  35.         return res;
  36.     }
  38.     public static int knapSack(int[] w, int[] v, int C) {
  39.         int size = w.length;
  40.         memo = new int[size][C + 1];
  41.         return solveKS(w, v, size - 1, C);
  42.     }
  44.     public static void main(String[] args) {
  45.         int[] w = {2, 1, 3, 2};
  46.         int[] v = {12, 10, 20, 15};
  47.         System.out.println(knapSack(w, v, 5));
  48.     }
  49. }

V3.0——动态规划算法

假如我们现在有三个物品，物品的重量和价值如下表所示，背包的最大容量是5
彻底理解0-1背包问题 - 图20
通过上述信息，我们可以得到一张二维表，二维表中每一个空格对应的就是V1.0版本中提到的彻底理解0-1背包问题 - 图21#card=math&code=F%28n%2CC%29&id=M2zRh)

彻底理解0-1背包问题 - 图22
我们可以很轻松地填充二维表的第一行数据，所代表的含义是彻底理解0-1背包问题 - 图23#card=math&code=F%280%2CC%29&id=crElY)

即在背包容量从0到5时，选择物品0所能获得的最大价值

彻底理解0-1背包问题 - 图24
继续填充第二行数据，此时的含义是，当背包容量从0到5时，待选择物品为物品1时背包的最大价值

注意：我这里说的 不是 选择物品1时 也不是 不选择物品1时的背包最大价值，因为选或不选都有可能

除了第一行以外，其他行的计算都包含当前行物品选或不选的两种可能，按照上文的递推公式来计算

以下图中标记的位置为例，当背包容量为3，待选择为物品1时，此时我们只需要根据之前在表格中填充过的数据进行计算即可，这就是动态规划！
彻底理解0-1背包问题 - 图25
更具体点说，标记位置的值取自下面两种情况的最大值

  • 当选择将物品1放入背包时（前提是放得下），此时背包的最大价值为物品1的价值+二维表[0][1]处的值，因为现在的背包容量需要减去物品1所占用的空间（3-2=1）
  • 当不选择将物品1放入背包时，此时背包的最大价值为二维表中[0][3]的值

再给大家看一遍递推公式，好好品味一下上面的这个关系，你肯定能搞明白

彻底理解0-1背包问题 - 图26%3Dmax(F(i-1%2CC)%2Cv(i)%2BF(i-1%2CC-w(i)))%0A#card=math&code=F%28i%2CC%29%3Dmax%28F%28i-1%2CC%29%2Cv%28i%29%2BF%28i-1%2CC-w%28i%29%29%29%0A&id=WluIQ)

  1. public class KnapSack01 {
  2.     public static int knapSack(int[] w, int[] v, int C) {
  3.         int size = w.length;
  4.         if (size == 0) {
  5.             return 0;
  6.         }
  8.         int[][] dp = new int[size][C + 1];
  10.         //初始化第一行
  11.         //仅考虑容量为C的背包放第0个物品的情况
  12.         for (int i = 0; i <= C; i++) {
  13.             dp[0][i] = w[0] <= i ? v[0] : 0;
  14.         }
  16.         //填充其他行和列
  17.         for (int i = 1; i < size; i++) {
  18.             for (int j = 0; j <= C; j++) {
  19.                 dp[i][j] = dp[i - 1][j];
  20.                 if (w[i] <= j) {
  21.                     dp[i][j] = Math.max(dp[i][j], v[i] + dp[i - 1][j - w[i]]);
  22.                 }
  23.             }
  24.         }
  26.         return dp[size - 1][C];
  27.     }
  29.     public static void main(String[] args) {
  30.         int[] w = {2, 1, 3, 2};
  31.         int[] v = {12, 10, 20, 15};
  32.         System.out.println(knapSack(w, v, 5));
  33.     }
  34. }

V4.0——动态规划空间复杂度的极致优化

上面的动态规划算法使用了彻底理解0-1背包问题 - 图27#card=math&code=O%28n%2AC%29&id=kOLH2)的空间复杂度（因为我们使用了二维数组来记录子问题的解）

其实我们完全可以只使用一维数组来存放结果，但同时我们需要注意的是，为了防止计算结果被覆盖，我们必须从后向前分别进行计算。为什么呢？往下看。

彻底理解0-1背包问题 - 图28

我们仍然假设背包空间为5，根据

彻底理解0-1背包问题 - 图29%3Dmax(F(i-1%2CC)%2Cv(i)%2BF(i-1%2CC-w(i)))%0A#card=math&code=F%28i%2CC%29%3Dmax%28F%28i-1%2CC%29%2Cv%28i%29%2BF%28i-1%2CC-w%28i%29%29%29%0A&id=s4eLT)

我们可以知道，当我们利用一维数组进行记忆化的时候，我们只需要使用到当前位置的值和该位置之前的值，举个例子

假设我们要计算彻底理解0-1背包问题 - 图30#card=math&code=F%28i%2C4%29&id=fIfUb),我们需要用到的值为彻底理解0-1背包问题 - 图31#card=math&code=F%28i-1%2C4%29&id=Om8EH)和彻底理解0-1背包问题 - 图32)#card=math&code=F%28i-1%2C4-w%28i%29%29&id=il7Kv),因此为了防止结果被覆盖，我们需要从后向前依次计算结果

经过V3.0版本的思考，你们画个图就能理解刚才的解释了，给出最终的动态规划代码

  1. public class KnapSack01 {
  2.     public static int knapSack(int[] w, int[] v, int C) {
  3.         int size = w.length;
  4.         if (size == 0) {
  5.             return 0;
  6.         }
  8.         int[] dp = new int[C + 1];
  10.         //初始化第一行
  11.         //仅考虑容量为C的背包放第0个物品的情况
  12.         for (int i = 0; i <= C; i++) {
  13.             dp[i] = w[0] <= i ? v[0] : 0;
  14.         }
  16.         for (int i = 1; i < size; i++) {
  17.             for (int j = C; j >= w[i]; j--) {
  18.                 dp[j] = Math.max(dp[j], v[i] + dp[j - w[i]]);
  19.             }
  20.         }
  21.         return dp[C];
  22.     }
  24.     public static void main(String[] args) {
  25.         int[] w = {2, 1, 3, 2};
  26.         int[] v = {12, 10, 20, 15};
  27.         System.out.println(knapSack(w, v, 5));
  28.     }
  29. }

利用背包问题的思想解决问题

leetcode 416 Partition Equal Subset Sum

给定一个仅包含正整数的非空数组，确定该数组是否可以分成两部分，要求两部分的和相等

问题分析

该问题我们可以利用背包问题的思想进行求解。

假设给定元素个数为彻底理解0-1背包问题 - 图33的数组arr，数组元素的和为sum，对应于背包问题，等价于有彻底理解0-1背包问题 - 图34个物品，每个物品的重量和价值均为为arr[i]，背包的限重为sum/2，求解背包中的物品最大价值为多少？

  1. class Solution {
  2.     private boolean knapSack(int[] nums,int sum){
  3.         int size = nums.length;
  5.         boolean[] dp = new boolean[sum + 1];
  6.         for (int i = 0;i <= sum;i ++){
  7.            dp[i] = i == nums[0];
  8.         }
  10.         for (int i = 1;i < size;i++){
  11.             for (int j = sum;j >= nums[i];j--){
  12.                 dp[j] = dp[j] || dp[j-nums[i]];
  13.             }
  14.         }
  15.         return dp[sum];
  16.     }
  18.     public boolean canPartition(int[] nums) {
  19.         int sum = 0;
  20.         for (int item : nums){
  21.             sum += item;
  22.         }
  24.         //如果数组元素和不是2的倍数，直接返回false
  25.         if (sum % 2 != 0)
  26.             return false;
  28.         return knapSack(nums,sum/2);
  29.     }
  30. }