力扣：416. 分割等和子集

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

此时背包大小为sum/2，物品的标号即下标，物品的重量和价值一样都为数组值，物品只允许放入一次。

二维背包实现代码：
一：确定dp数组的含义
dp[ i ][j]：从物品为0~i中选择投入重量为 j的背包所产生的最大价值
二：dp递归公式
此时分为最后一个物品是否加入，或者想象图形。
dp[i][j] = max(dp[i-1][j-nums[i]]+nums[i],dp[i-1][j]);
三：初始化 在脑海中想象图像当前值是由上面一个值和左上角的一个值所决定的
对于二维是：
dp【i】【j】 = max(dp【i-1】【j-nums【i】】+nums【i】,dp【i-1】【j】);
四：遍历顺序
随便遍历，先 i 先 j 都行。

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int sum = 0;
        for(int i = 0; i < nums.size(); ++i){
            sum += nums[i];
        }
        if(sum%2 != 0) return false;
        int bagweight = sum/2;
        vector<vector<int>> dp (200,vector<int>(20001,0));
        for(int j = nums[0]; j <= bagweight; ++j){
            dp[0][j] = nums[0];
        }
        for(int i = 1; i < nums.size();++i){
            for(int j = 1; j <= bagweight; ++j){
                if(j < nums[i]) dp[i][j] = dp[i-1][j];
                else dp[i][j] = max(dp[i-1][j-nums[i]]+nums[i],dp[i-1][j]);
            }
        }
        if(dp[nums.size()-1][sum/2] == sum/2) 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

一维背包实现代码
一：确定dp数组的含义
dp[ j ]：背包重量为 j 所产生的最大价值
二：dp递归公式
dp[j] = max(dp[j],dp[j-nums[i]]+nums[i]);
三：初始化 在脑海中想象图像当前值是由上面一个值和左上角的一个值所决定的
对于二维是：
dp【i】【j】 = max(dp【i-1】【j-nums【i】】+nums【i】,dp【i-1】【j】);
对于一维是：
dp【j】 = max(dp【j】,dp【j-nums【i】】+nums【i】);
四：遍历顺序
从尾到头遍历，同时应该背包重量大于物品重量才进入这个for，即 结束条件 j >= nums[i]而不是j >= 0。

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int sum = 0;
        for(int i = 0; i < nums.size(); ++i){
            sum += nums[i];
        }
        if(sum%2 != 0) return false;
        int bagweight = sum/2;
        vector<int> dp(10001,0);
        for(int i = 0; i < nums.size(); ++i){
            for(int j = bagweight; j >= nums[i] ; --j){
                dp[j] = max(dp[j],dp[j-nums[i]]+nums[i]);
            }
        }
        if(dp[bagweight] == bagweight) 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