代码随想录算法训练营第四十二天 | 01背包问题、416. 分割等和子集

01背包问题

文章讲解/视频讲解：https://programmercarl.com/%E8%83%8C%E5%8C%85%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%8001%E8%83%8C%E5%8C%85-1.html

01背包的理论基础，以及推导过程参考上述代码随想录中的链接。

这道题在卡码网上有原题，题目链接为：https://kamacoder.com/problempage.php?pid=1046

使用二维dp数组的实现：

#include<iostream>
#include<vector>
 
using namespace std;
 
 
int main(){
    int M, N;
    cin>>M>>N;
    vector<int> weight(M, 0);
    for(int i = 0;i<M;i++)
        cin>>weight[i];
    vector<int> value(M, 0);
    for(int i = 0;i<M;i++)
        cin>>value[i];
         
    vector<vector<int>> dp(M, vector<int>(N + 1, 0));
    for(int j = weight[0];j<=N;j++)
        dp[0][j] = value[0];
     
    for(int i = 1;i<M;i++){
        for(int j = 0;j<=N;j++){
            if(j<weight[i]) dp[i][j] = dp[i - 1][j];
            else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
        }
    }
     
    cout<<dp[M - 1][N]<<endl;
     
     
    return 0;
}

一维滚动数组的写法：

#include<iostream>
#include<vector>

using namespace std;


int main(){
    int M, N;
    cin>>M>>N;
    vector<int> weight(M, 0);
    for(int i = 0;i<M;i++)
        cin>>weight[i];
    vector<int> value(M, 0);
    for(int i = 0;i<M;i++)
        cin>>value[i];
    
    vector<int> dp(N + 1, 0);
    for(int j = weight[0];j<=N;j++)
        dp[j] = value[0];
        
    for(int i = 1;i<M;i++){
        for(int j = N;j>=weight[i];j--){
            dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
        }
    }
    
    cout<<dp[N]<<endl;
    
    return 0;
}

注意：压缩成一维数组之后，内层循环的遍历顺序发生了改变，这是因为一维dp数组相当于dp[i][j]将dp[i-1][j]覆盖，如果j从前往后遍历，那么递推公式就等价于

dp[i][j] = max(dp[i - 1][j], dp[i][j - weight[i]] + value[i]);

因为dp[j - weight[i]]已经被更新过，此时等价于dp[i][j - weight[i]]，而不是dp[i - 1][j - weight[i]]。如果想要在遍历到dp[j]时，dp[j - weight[i]]没有被更新过，那就只能从后往前遍历。

416. 分割等和子集

题目链接：416. 分割等和子集

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

文章讲解/视频讲解：https://programmercarl.com/0416.%E5%88%86%E5%89%B2%E7%AD%89%E5%92%8C%E5%AD%90%E9%9B%86.html

思路

首先从二维dp数组开始思考。设置一个二维bool类型的dp数组，dp[i][j]代表当前0 ~ i下标的正整数能否产生和为j的组合。

然后进行初始化，对于第一层的初始化而言，只有当j = nums[0]时，第一层的dp数值为true，其余全为false。dp数组的递推式为：

dp[i][j] = j == nums[i] || dp[i - 1][j] || dp[i - 1][j - nums[i]];

由于此时是二维数组，所以遍历顺序没有太大影响，i与j均从小到达遍历即可。

接着可以考虑将二维dp数组压缩为一维滚动数组，类似01背包中的数组压缩，在第二层遍历j时，从后往前遍历即可。

看了卡哥的教程，这里的dp数组也可以定义为：dp[j]表示背包总容量是j，放进物品后，背的最大重量为dp[j]。

C++实现

// 二维dp写法
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;

        vector<vector<bool>> dp(nums.size(), vector<bool>(sum / 2 + 1, false));
        // 初始化
        for(int j = 0;j<= sum / 2;j++){
            if(j == nums[0]) dp[0][j] = true;
        }

        for(int i = 1;i<nums.size();i++){
            for(int j = 0;j<=sum / 2;j++){
                if(j < nums[i]) dp[i][j] = dp[i - 1][j];
                else{
                    dp[i][j] = dp[i - 1][j] || j == nums[i] || dp[i - 1][j - nums[i]];
                }
            }
        }
        return dp[nums.size() - 1][sum / 2];
    }
};

// 一维滚动dp数组
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;

        vector<bool> dp(sum / 2 + 1, false);

        // 初始化
        for(int j = 0;j<= sum / 2;j++){
            if(j == nums[0]) dp[j] = true;
        }

        for(int i = 1;i<nums.size();i++){
            for(int j = sum / 2;j>=nums[i];j--){
                if(dp[j]) continue;
                dp[j] = j == nums[i] || dp[j - nums[i]];
            }
        }

        return dp[sum / 2];
    }
};

// 代码随想录中的写法
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;

        vector<int> dp(sum / 2 + 1, 0);
        
        for(int j = nums[0];j<=sum / 2;j++){
            dp[j] = nums[0];
        }

        for(int i = 1;i<nums.size();i++){
            for(int j = sum / 2;j >= nums[i];j--){
                dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);
            }
        }
        return dp[sum / 2] == sum / 2;
    }
};