leetcode416分割等和子集刷题打卡

416. 分割等和子集 - 力扣（Leetcode）

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

示例 1：

输入：nums = [1,5,11,5]
输出：true
解释：数组可以分割成 [1, 5, 5] 和 [11] 。
1
2
3

示例 2：

输入：nums = [1,2,3,5]
输出：false
解释：数组不能分割成两个元素和相等的子集。
1
2
3

提示：

• 1 <= nums.length <= 200
• 1 <= nums[i] <= 100

题解思路

给出背包问题，大家都知道，有N件物品和一个最多能背重量为W 的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。

这道题目是要找是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。那么只要找到集合里能够出现 sum / 2 的子集总和，就算是可以分割成两个相同元素和子集了。

可以使用01背包来解题，元素不能重复取，所以使用01背包

首先需要确定以下几点：

• 有几个物品可供选择：nums.size()
• 背包的总容量是多少：accumulate(nums.)/2
  • 因为题目是要求出现两个子集，其和相等都为sum/2
• 物品重量如何表示：nums[i]
• 物品价值如何表示：nums[i]

动归五步：

二维dp

• 确定dp数组及其含义

  • dp[i][j]代表从[0, i]中选择一件物品放入容量大小为j的背包所能获得的最大价值

• 确定递推公式

  • dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - nums[i]] + nums[i])

    这是01背包的标准格式，dp[i][j]可以由dp[i - 1][?]推出，取第i件物品与不取第i件物品两种取最大值

• 确定dp数组的初始化

  • dp[0][0]同列初始化为0 因为根据定义dp[i][0]代表从[0,i]中选择一件物品放入背包容量为0的背包中获得的最大价值，此处背包容量为0，所以第0列全部初始化为0，初始化第0行的时候也要根据定义，第0行代表就是选择第0件物品放入背包容量为j的背包中，所以只要背包装得下第0件物品，就初始化该位置为其价值

    for(int i = nums[0]; i <= target; i++){
        dp[0][i] = nums[0];
    }
    1
    2
    3

• 确定递推顺序

  • 二维dp数组遍历顺序很自由，我这里先顺序遍历物品，再顺序遍历容量

• 手动推导dp数组

  • 手写一下，看运行后是否与自己想的是否有区别来修改自己的代码

一维dp（滚动数组）

• 确定dp数组及其含义

  • dp[j]表示容量为j的背包所能获得的最大价值，相较于二维dp数组，其就是将上一层复制到了下一层，因而后续递推公式是和自己比较

• 确定递推公式

  • dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);

• 确定dp数组的初始化

  • dp[0]为背包容量为0，什么都装不了，肯定初始化为0，后续的值则dp数组在推导的时候一定是取价值最大的数，如果题目给的价值都是正整数那么非0下标都初始化为0就可以了。当然如果题目给出数组中有负数，则要初始化为INT_MIN来避免覆盖

• 确定递推顺序

  • 首先给出代码

    for(int i = 0; i < nums.size(); i++){
        for(int j = target; j >= nums[i]; j--){
            dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);
        }
    }
    1
    2
    3
    4
    5

    可以看见，与二维dp相比，其遍历容量的时候是倒叙遍历的，这是为了保证保证物品i只被放入一次！。但如果一旦正序遍历了，那么物品0就会被重复加入多次！

    换个说法：因为i每加1代表新的一行开始，由于dp[j-num[i]]每次都得使用的是上一行的数据。但是如果你正序的话，那么你在计算dp[j]的时候用到的dp[j-num[i]]是本行的，而不是上一行的，所以用逆序，逆序用到的dp[j-num[i]]是上一行的。

• 手动推导dp数组

  • 手写一下，看运行后是否与自己想的是否有区别来修改自己的代码

完整代码

class Solution {
public:
    bool canPartition(vector& nums) {
        // 有几个物品可供选择  ->  nums.size()  ->  用于i
        // 背包的总容量是多少  ->  accumulate(nums.)/2  ->用于j
        // 物品重量如何表示  ->  nums[i]  ->  weight[i]
        // 物品价值如何表示  ->  nums[i]  ->  value[i]
        int sum = accumulate(nums.begin(), nums.end(), 0);

        if(sum % 2 == 1) return false;

        int target = sum / 2;

        // 一维数组
        /*vector dp(target + 1, 0);
        // 默认全体初始化为0
        for(int i = 0; i < nums.size(); i++){
            for(int j = target; j >= nums[i]; j--){
                dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);
            }
        }
        if(dp[target] == target) return true;
        */
        // 二维数组
        vector> dp(nums.size(), vector(target + 1, 0));
        // 初始化
        // dp[0][0]同列初始化为0  因为根据定义dp[i][0]代表从[0,i]中选择一件物品放入背包容量为0的背包中获得的最大价值，此处背包容量为0，所以第0列全部初始化为0，初始化第0行的时候也要根据定义，第0行代表就是选择第0件物品放入背包容量为j的背包中，所以只要背包装得下第0件物品，就初始化该位置为其价值
        for(int i = nums[0]; i <= target; i++){
            dp[0][i] = nums[0];
        }
        for(int i = 1; i < nums.size(); i++){
            for(int j = 1; j <= target; j++){
                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]);
            }
        }
        
        if(dp[nums.size() - 1][target] == target) return true;
        return false;
    }
};
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
36
37
38
39
40
41