0-1 背包问题

问题定义

有一个背包，他的容量为 C (Capacity)。现在有n中不同的物品，编号为 0…n-1，其中每一件物品的重量为 w(i)，价值为 v(i)。问可以向这个背包中盛放哪些物品，使得在不超过背包容量的基础上，物品的总价值最大。

解决方法

状态定义

对于这类组合问题，需要用两个变量来定义状态。

用 f(n, c) 表示将 n 个物品放进容量为 c 的背包可以获得的最大值。

状态转移

对于物品 i，有两个选择：不放进背包和放进背包，对应的结果分别为 f(i-1, c) 和 f(i-1, c-w[i]) + v[i] 。

f(i, c) = max{ f(i-1, c), f(i-1, c-w(i)) + v(i) }

动态规划

// Java 二维数组实现
public int knapstack01(int[] w, int[] v, int C) {
    // 初始化 dp[0][c]=0
    int n = w.length; // 物品数量
    int[][] dp = new int[n][C+1];
    
    // 递推
    for (int i = 0; i < n; i++) {
        for (int c = 1; c <= C; c++) {
            if (w[i] > c) { // 放不进背包
                dp[i][c] = dp[i - 1][c];
            } else {
                dp[i][c] = Math.max(dp[i - 1][c], dp[i - 1][c - w[i]] + v[i]);
            }
        }
    }
  
    return dp[n][C];
}

时间复杂度和空间复杂度均为 O(nC)。

空间优化

根据状态转义方程可以看出，i 个物品的结果只依赖于 i-1 个物品的结果，所以我们在动规时只需要记录上次的结果。

// Java 两行数组实现
public int knapstack01(int[] w, int[] v, int C) {
    // 初始化 dp[0][c]=0
    int n = w.length; // 物品数量
    int[][] dp = new int[2][C+1];
    
    // 递推
    for (int i = 0; i < n; i++) {
        for (int c = 1; c <= C; c++) {
            if (w[i] > c) { // 放不进背包
                dp[i % 2][c] = dp[(i - 1) % 2][c];
            } else {
                dp[i % 2][c] = Math.max(dp[(i - 1) % 2][c], dp[(i - 1) % 2][c - w[i]] + v[i]);
            }
        }
    }
  
    return dp[n % 2][C];
}

空间复杂度：O(2C)

其实我们还可以只用一个一维数组。

// Java 一维数组实现
public int knapstack01(int[] w, int[] v, int C) {
    // 初始化 dp[0][c]=0
    int n = w.length; // 物品数量
    int[] dp = new int[C+1];
    
    // 递推
    for (int i = 0; i < n; i++) {
        for (int c = C; c >= w[i]; c++) { // 注意要逆序，而且只遍历到 c>=w[i] 即可
            // 因为逆序时，计算 i 个物品的 dp[c] 时，dp[c - w[i]] 才表示 i-1 个物品时的结果
            // 如果是正序，计算 i 个物品的 dp[c] 时，dp[c - w[i]] 已经是 i 个物品时的结果
            dp[c] = Math.max(dp[c], dp[c - w[i]] + v[i]);
        }
    }
  
    return dp[C];
}

问题变种

分割等和子集

给定一个只包含正整数的非空数组 nums。是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

来源：https://leetcode-cn.com/problems/partition-equal-subset-sum/

问题转换：假设所以正数的和为 sum，那么问题就可以转换为求是否存在一组数的和刚好为 sum/2。

对应背包问题：背包容量 C=sum/2，物品数量 n=nums.length，状态 f(i, c) 表示给定 i 个物品时是否存在一组物品的重量和刚好为 c，状态转移方程为 f(i, c) = f(i-1, c) || f(i-1, c-w[i])。

class Solution {
    public boolean canPartition(int[] nums) {
        int sum = 0;
        for (int x : nums) {
            sum += x;
        }
        if (sum % 2 > 0) {
          return false; // 总和为奇数时，不可能划分成两个相等的子集
        }
        
        int n = nums.length;
        int C = sum / 2;
        int[] w = nums;
        boolean[] dp = new boolean[C + 1];
        
        // 初始化，对应第 0 个物品，只有容量 c==w[i] 时，状态 dp[c]=true
        // 也可简化为 if (nums[0] <= C) dp[nums[0]] = true;
        for (int c = 0; c <= C; c++) {
            dp[c] = c == nums[0];
        }
      
        // 自底向上迭代
        for (int i = 1; i < n; i++) {
            for (int c = C; c >= w[i]; c--) {
                dp[c] = dp[c] || dp[c - w[i]];
            }
        }
        
        return dp[C];
    }
}

最后一块石头的重量

有一堆石头，每块石头的重量都是正整数。

每一回合，从中选出任意两块石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下：

• 如果 x == y，那么两块石头都会被完全粉碎；
• 如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x。

最后，最多只会剩下一块石头。返回此石头最小的可能重量。如果没有石头剩下，就返回 0。

链接：https://leetcode-cn.com/problems/last-stone-weight-ii

问题转化：由于石头拿走还能放回去，因此可以简单地把所有石头看作两堆，假设总重量为 sum，如何使两堆石头总重量接近 sum/2。

对应背包问题：背包容量 C=sum/2，物品数量为石头个数 n，状态 f(i, c) 表示给定 i 个物品时最大容量为 c 时背包的重量，状态转移方程为 f(i, c) = max{ f(i-1, c), f(i-1, c-w[i]) + w[i] }。

class Solution {
    public int lastStoneWeightII(int[] stones) {
        int sum = 0;
        for (int i : stones) {
            sum += i;
        }
        /* 定义 dp[i] 重量上限为 i 时背包所能装载的最大石头重量 */
        int n = stones.length;
        int C = sum/2;
        int[] w = stones;
        int[] dp = new int[C + 1];
        for (int i = 0; i < n; i++) {
            int curStone = stones[i];
            for (int c = C; j >= w[i]; c--) {
                dp[c] = Math.max(dp[c], dp[c - w[i]] + w[i]);
            }
        }
        return sum - 2 * dp[maxCapacity];
    }
}

–

参考资料：

• https://juejin.im/post/5b40c99ee51d45190b615f33#heading-15 leetcode题解（0-1背包问题）
• https://www.zhangjc.site/archives-327/ 1049. 最后一块石头的重量 II - Last Stone Weight II