LeetCode 416. 分割等和子集（dp背包问题）

暴力回溯

class Solution {
public:
    int curSum;
    int target;

    bool func(int startIndex, const vector<int>& nums){
        if(curSum == target){
            return true;
        }
        for(int i = startIndex; i < nums.size(); i++){
            curSum += nums[i];
            if(func(i + 1, nums)){
                return true;
            }
            curSum -= nums[i];
        }
        return false;
    }

    bool canPartition(vector<int>& nums) {
        curSum = 0;
        int num = accumulate(nums.begin(), nums.end(), 0);
        if(num % 2 != 0){
            return false;
        }
        target = num / 2;
        return func(0, nums);
    }
};
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
26
27
28
29

常规二维01背包

其实就是在数组中找一个子集，使得子集的和等于所有数和的一半，将和的一半记为target。我们用一个容量为target的背包，装入数组中的物品，如果刚好能装满，说明可以找到一个子集的和为target

只有确定了如下四点，才能把01背包问题套到本题上来

• 背包的体积为sum / 2
• 背包要放入的商品（集合里的元素）重量为 元素的数值，价值也为元素的数值
• 背包如果正好装满，说明找到了总和为 sum / 2 的子集
• 背包中每一个元素是不可重复放入，不是完全背包问题

01背包的递推公式为：dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight[i]] + value[i])

本题递推公式：dp[i][j] = max(dp[i-1][j], dp[i-1][j-nums[i]] + nums[i])

bool canPartition(vector<int>& nums) {
        int num = accumulate(nums.begin(), nums.end(), 0);
        if (num % 2 != 0) {
            return false;
        }
        int target = num / 2;
        int n = nums.size();
        vector<vector<int>> dp(n, vector<int>(target + 1, 0));
        // 二维数组填表，先遍历物品，再遍历背包容量
        for (int i = 0; i < n; i++) {
        	// j一定要是[1,target]，不仅仅是下标，还是有物理含义的，表示背包的容量大小，多以不能是[0,target-1]
            for (int j = 1; j <= target; j++) {
                if (i == 0) {
                	// 只有一个物品时，容量小于物品重量，装不下，装入0
                    if (j < nums[i]) {
                        dp[i][j] = 0;
                    }
                    else {
                    	// 只有一个物品时，容量不小于物品重量，装入
                        dp[i][j] = nums[i];
                    }
                }
                else {
                    if (j < nums[i]) {
                        // 当前容量小于物品重量
                        dp[i][j] = dp[i - 1][j];
                    }
                    else {
                        dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - nums[i]] + nums[i]);
                    }
                }
            }
        }
        return dp[n-1][target] == target; // 一半容量刚好装入target重量的物品时，返回true
    }
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
26
27
28
29
30
31
32
33
34
35

滚动数组

对于背包问题其实状态都是可以压缩的，在使用二维数组解01背包问题的时候，递推公式为：dp[i][j] = max(dp[i-1][j], dp[i-1][j - weight[i]] + value[i])，计算当前层的值，只需要使用上一层的数据即可

其实如果把 dp[i - 1]那一层拷贝到dp[i]上，表达式完全可以是：dp[i][j] = max(dp[i][j], dp[i][j - weight[i]] + value[i])，旧的dp[i][j]就是上一层的dp[i-1][j]，新的dp[i][j]就是当前层的值

如果我们将二维dp数组改为一维dp数组，我们需要倒着遍历背包容量：

// 遍历物品
for(int i = 0; i < weight.size(); i++) { 
	// 遍历背包容量
    for(int j = bagWeight; j >= weight[i]; j--) { 
        dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
    }
}
1
2
3
4
5
6
7

为什么需要倒着遍历背包容量？

在二维dp数组中，计算当前层只需要使用上一层正上方的dp[i-1][j]和左上方的dp[i-1][j - weight[i]]即可。而在一维dp数组中，我们在计算当前层某个值时，希望使用数据是没有被修改的，所以需要从后往前填表

举个例子：

比如说在填写二维数组时，我们使用上一层的3和5推导出了下一层的7，如果这是一维滚动数组，这个7就会覆盖上面的5，如果我再计算🔺位置的值时，就会使用到更新后的7，而不是更新前的5，这就会出现问题

如果我们从后往前填表，在一维滚动数组中，由于计算当前值，只使用左侧或者上方的值，只要保证当前值左侧/上方的值都没有被修改，即可保证结果和二维dp数组一样正确

使用一维dp数组的代码如下：

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int num = accumulate(nums.begin(), nums.end(), 0);
        if (num % 2 != 0) {
            return false;
        }

        int target = num / 2;
        int n = nums.size();
        vector<int> dp(target + 1, 0);

        // 先填写i=0，只有一个物品的情况
        for(int j = nums[0]; j <= target; j++){
            dp[j] = nums[0];
        }
        // 遍历物品
        for (int i = 1; i < n; i++) {
            // 遍历背包容量
            for (int j = target; j >= 1; j--) {
            	// 这里不能是j <= nums[i]，因为当前容量j==nums[i]时，也要通过计算，来决定是否将nums[i]放入背包
                if(j < nums[i]){
                    // 当前容量小于物品重量，取上一层的结果
                    dp[j] = dp[j];
                }else{
                    dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);
                }
            }
        }
        return dp[target] == target;
    }
};
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
26
27
28
29
30
31
32

在遍历背包容量的for循环中，当背包容量j小于当前物品重量nums[i]时应该是取上一层的结果，在一维数组中就是不做操作，代码改为如下：

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int num = accumulate(nums.begin(), nums.end(), 0);
        if (num % 2 != 0) {
            return false;
        }

        int target = num / 2;
        int n = nums.size();
        vector<int> dp(target + 1, 0);

        // 先填写i=0，只有一个物品的情况
        for(int j = nums[0]; j <= target; j++){
            dp[j] = nums[0];
        }
        // 遍历物品
        for (int i = 1; i < n; i++) {
            // 遍历背包容量
            // 这里一定要j >= nums[i]，不能是j > nums[i]，因为背包容量和当前物品容量相等时，也要判断是否装入当前物品
            for (int j = target; j >= nums[i]; j--) {
                dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);
            }
        }
        return dp[target] == target;
    }

};
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
26
27
28