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

题目链接： 01背包问题二维

思路

代码

题目链接：01背包问题一维

思路

代码

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

思路

代码

总结

题目链接：01背包问题二维

思路

①dp数组，物品从下标0到i的物品中任取，然后放进容量为j的背包里，此时最大的价值

②递推公式，到第i个物品时有两个选择，放或者不放。如果不放，最大价值就是dp[i-1][j]，说明第i个物品太大了放不下，价值还是和i-1的状态一样；如果放，最大价值就是i-1时的价值加上value[i]，即dp[i-1][j-wight[i]]+value[i]。也就是说当前dp[i][j]可以由这两个状态推导而来，因为要取最大价值，所以取这两个值中的最大值

③dp数组初始化，由递推公式可知，dp数组当前值可由左上角和正上方两个方向推导而来，所以只需要初始化第一列和第一行即可由递推公式得到整个二维dp数组。当背包容量为0时，放不了东西，所以这一列初始化为0；下标为物品0时，如果背包容量足够就将其初始化为物品0的价值，如果放不下就初始化为0

④遍历顺序，由递推公式可知，只要有左上角和上方的值即可推导当前值，所以先遍历行或者列，或者说先遍历物品或者背包都可以

⑤推导dp数组

代码

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int m,n;//m为物品个数，n为背包空间
void solve(){
    vector<int> weight(m,0);//物品重量
    vector<int> value(m,0);//物品价值
    vector<vector<int>> dp(m,vector<int>(n+1,0));//dp数组
    //输入重量和价值
    for(int i = 0; i < m; i++){
        cin>>weight[i];
    }
    for(int i = 0; i < m; i++){
        cin>>value[i];
    }
    //当第一个物品的重量小于背包空间时
    //此时dp赋值为该物品的value
    for(int j = weight[0]; j <= n; j++){
        dp[0][j] = value[0];
    }
    //遍历背包
    for(int j = 0; j <= n; j++){
        //遍历物品，物品从1到i
        for(int i = 1; i < m; i++){
            if(weight[i] > j) 
                //装不下时，价值与遍历到上一个物品时一样
                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;
    
}

int main(){
    while(cin>>m>>n){
        solve();
    }
    return 0;
}

题目链接：01背包问题一维

思路

①dp数组，容量为j的背包，能装的物品价值最大为dp[j]

②递推公式，与二维类似，只不过用了一维的滚动数组。此时背包空间为j，有两个选择：装不下当前物品，则此时背包的价值与遍历上一个物品时一样，也就是dp[j] = dp[j-weight[i]]；能装下时，有两种情况，装完后价值比之前大，装完后价值比之前小，肯定是二者选最大。装之前，dp[j] = dp[j-weight[i]]，装之后，dp[j] = dp[j-weight[i]] + value[i]。

③dp数组初始化，根据递推公式可知背包空间为0时装不了物品，所以价值为0即dp[0] = 0，往后遍历时会进行更新，所以其他位置先初始化为0即可。

④遍历顺序，先物品，后背包，且背包倒序遍历，从空间最大往前遍历。因为是先遍历物品，如果背包正序遍历，则物品i可能会被重复放入。

⑤推导dp数组

代码

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

//一维dp数组
int m,n;//m为物品种类，n为背包容量
void solve(){
    vector<int> weight(m,0);
    vector<int> value(m,0);
    //dp[n]的意义是背包容量为n的时候，所装物品的最大价值为dp[n]
    //因为dp数组从0开始，所以dp数组的大小为n+1
    vector<int> dp(n+1,0);
    //输入物品信息，重量和价值
    for(int i = 0; i < m; i++){
        cin>>weight[i];
    }
    for(int i = 0; i < m; i++){
        cin>>value[i];
    }
    //遍历顺序，先物品，后背包，其背包倒序遍历
    //由于dp数组大小有限，并不会保存上一层的信息
    //所以要先遍历物品，把当前物品处理完再进行下一层
    //背包倒序遍历是防止同一物品被多次装入背包
    for(int i = 0; i < m; i++){
        //如果能装下才对dp数组当前位置进行更新
        for(int j = n; j >=weight[i]; j--){
            dp[j] = max(dp[j],dp[j-weight[i]]+value[i]);
        }
    }
    cout<<dp[n]<<endl;
}

int main(){
    while(cin>>m>>n){
        solve();
    }
    return 0;
}

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

思路

将该题归类为01背包问题

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

①dp数组，容量为j的背包所装物品的最大价值为dp[j]，本题所给的数组既是重量也是价值

②递推公式，dp[j] = max[dp[j], dp[j-nums[i]]+nums[i]]

③dp数组初始化，本题所给数组中的数都是正整数，所以初始化为0即可

④遍历顺序，滚动数组，先物品后背包，背包倒序

⑤推导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 == 1)
            return false;
        // target为背包的容量
        int target = sum / 2;
        vector<int> dp(target + 1, 0); // 定义dp数组
        // 01背包，先物品，后背包，背包倒序遍历
        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;
        return false;
    }
};