0-1背包问题和LeetCode 416.分割等和子集

发表于 | 分类于 |

※ 0-1背包

有一个容量为 N 的背包，要用这个背包装下物品的价值最大，这些物品有两个属性：体积 w 和价值 v。

定义一个二维数组 dp 存储最大价值，其中 $dp[i][j] $表示前 i 件物品体积不超过 j 的情况下能达到的最大价值。设第 i 件物品体积为 w，价值为 v，根据第 i 件物品是否添加到背包中，可以分两种情况讨论：

  • 第 i 件物品没添加到背包，总体积不超过 j 的前 i 件物品的最大价值，就是总体积不超过 j 的前 i-1 件物品的最大价值，$dp[i][j] = dp[i-1][j]$。
  • 第 i 件物品添加到背包中，$dp[i][j] = dp[i-1][j-w] + v$。

第 i 件物品可添加也可以不添加，取决于哪种情况下最大价值更大。因此，0-1 背包的状态转移方程为：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// W 为背包总体积
// N 为物品数量
// weights 数组存储 N 个物品的重量
// values 数组存储 N 个物品的价值
public int knapsack(int W, int N, int[] weights, int[] values) {
    int[][] dp = new int[N + 1][W + 1];
    for (int i = 1; i <= N; i++) {
        int w = weights[i - 1], v = values[i - 1];
        for (int j = 1; j <= W; j++) {
            if (j >= w) {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - w] + v);
            } else {
                dp[i][j] = dp[i - 1][j];
            }
        }
    }
    return dp[N][W];
}

空间优化

在程序实现时可以对 0-1 背包做优化。观察状态转移方程可以知道，前 i 件物品的状态仅与前 i-1 件物品的状态有关，因此可以将 dp 定义为一维数组，其中 $dp[j]$ 既可以表示 $dp[i-1][j]$ 也可以表示$ dp[i][j]$。此时，

因为 $dp[j-w] $表示 $dp[i-1][j-w]$，因此不能先求 $dp[i][j-w]$，防止将 $dp[i-1][j-w] $覆盖。也就是说要先计算 $dp[i][j] $再计算 $dp[i][j-w]$，在程序实现时需要按倒序来循环求解。

1
2
3
4
5
6
7
8
9
10
11
12
public int knapsack(int W, int N, int[] weights, int[] values) {
    int[] dp = new int[W + 1];
    for (int i = 1; i <= N; i++) {
        int w = weights[i - 1], v = values[i - 1];
        for (int j = W; j >= 1; j--) {
            if (j >= w) {
                dp[j] = Math.max(dp[j], dp[j - w] + v);
            }
        }
    }
    return dp[W];
}

无法使用贪心算法的解释

0-1 背包问题无法使用贪心算法来求解，也就是说不能按照先添加性价比最高的物品来达到最优，这是因为这种方式可能造成背包空间的浪费，从而无法达到最优。考虑下面的物品和一个容量为 5 的背包，如果先添加物品 0 再添加物品 1，那么只能存放的价值为 16，浪费了大小为 2 的空间。最优的方式是存放物品 1 和物品 2，价值为 22.

id w v v/w
0 1 6 6
1 2 10 5
2 3 12 4

变种

  • 完全背包：物品数量为无限个
  • 多重背包：物品数量有限制
  • 多维费用背包：物品不仅有重量，还有体积，同时考虑这两种限制
  • 其它：物品之间相互约束或者依赖

416. 分割等和子集

416.Partition Equal Subset Sum (Medium)

Leetcode / 力扣

2020-7-28 15:46:15

题目描述

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

  • 每个数组中的元素不会超过 100
  • 数组的大小不会超过 200
1
2
3
4
示例 1:
输入: [1, 5, 11, 5]
输出: true
解释: 数组可以分割成 [1, 5, 5] 和 [11].

解题思路

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
    public boolean canPartition(int[] nums) {
        int sum = calcArraySum(nums);
        if(sum%2 != 0){
            return false;
        }
        int N = sum / 2;
        boolean[] dp = new boolean[N + 1];
        dp[0] = true;
        for(int num : nums){
            for(int j = N; j >= num; j--){
                dp[j] = dp[j] || dp[j - num];
            }
        }
        return dp[N];
    }

    private int calcArraySum(int[] nums){
        int sum = 0;
        for(int num : nums){
            sum += num;
        }
        return sum;
    }
}

为了防止True正序遍历被覆盖，所以倒着来。

上面这种写法节省了一定空间。完整的状态转移过程具体可以看下图，$dp[i][j] = dp[i-1][j]$ or $dp[i-1][j - nums[i]]$。