代码随想Day42 | 背包问题、416. 分割等和子集

首先这道题是在卡码网，需要自己写输入输出，整体的输入输出思路是：

需要三行，首先是两个正数M、N，接着是两个数组，把两个正数当作进入函数的循环条件，然后再进入函数之后定义数组，并依次赋值。

接下来是二维数组来解决01背包的详细思路：

首先是dp数组的定义：

dp[i][j]：任取[0-i]之间的物品放进容量为j的背包里的最大价值。

递推公式：

dp[i][j]有两种情况：一种不放物品i，一种是放物品i；

不放物品i为dp[i-1][j]；放物品i为dp[i-1][j-weight[i]]+value[i]，注意前一项是不放物品i的背包为j-weight[i]的容量的最大价值，因为后面要放物品i，所以需要腾出对应的重量；取这两项的最大值就是dp[i][j]。

dp初始化：

需要初始化第一行和第一列，因为后续都是依靠这两项递推，容量为0，最大价值为0；而第一行dp[0][j]则当j大于等于物品0的重量时等于物品0的价值。

遍历顺序：

通过模拟可以发现，两层循环先循环物品或者先循环背包都可以，依照个人喜好。

详细代码如下：

#include<iostream>
#include<vector>
using namespace std;
int m,n;
void solve()
{
    vector<int>weight(m,0);
    vector<int>value(m,0);
    for(int i=0;i<m;i++)
    {
        cin>>weight[i];
    }
    for(int i=0;i<m;i++)
    {
        cin>>value[i];
    }
    vector<vector<int>>dp(m,vector<int>(n+1,0));//M行N+1列
    for(int j=weight[0];j<=n;j++)
    {
        dp[0][j]=value[0]; //最大价值是第0件物品的价值
    }
    for(int i=1;i<m;i++)
    {
        for(int j=1;j<=n;j++)
        {
            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];
}
int main()
{
    while(cin>>m>>n)
    {
        solve();
    }
    return 0;
}

?01背包问题?一维?

变为一维主要是压缩空间，压缩物品维度。

dp[j]:容量为j的背包最大的价值；

递推：dp[j] = max(dp[j],dp[j-weight[i]]+value[i])，注意这里的dp[j]是代表不取物品i的情况；

初始化：初始化为物品0的时候的背包为j的最大价值；

遍历顺序：遍历背包容量时候需要倒序，倒序可以保证每个物品只取一次，主要是dp[j]需要用到dp[j-x]，正序遍历的时候前面的值已经被修改，而倒序则不被修改，相当于还是上层的值。

详细代码如下：

#include<iostream>
#include<vector>
using namespace std;
int m,n;
void solve()
{
    vector<int>weight(m,0);
    vector<int>value(m,0);
    for(int i=0;i<m;i++)
    {
        cin>>weight[i];
    }
    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]; //最大价值是第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];
}
int main()
{
    while(cin>>m>>n)
    {
        solve();
    }
    return 0;
}

?416.?分割等和子集??

本题是?01背包的应用类题目：

这道题需要分析出：体积是数组总和的1/2；

dp[j]：背包容量为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==1) return false;
        int targrt = sum/2;
        vector<int>dp(targrt+1,0);
        for(int i=0;i<nums.size();i++)
        {
            for(int j=targrt;j>=nums[i];j--)
            {
                dp[j]=max(dp[j],dp[j-nums[i]]+nums[i]);
            }
        }
        if(targrt==dp[targrt]) return true;
        return false;

    }
};