代码随想录算法训练营第41天|背包理论基础 滚动数组法 416.分割等和子集

背包理论基础

        终于开始刷大名鼎鼎的背包问题了，背包问题有点复杂，我还是懂了但没完全懂，下面是我现在的理解，我们把dp[i][j]定义为i个物品在背包容量为j下的价值，那么这样就转换为如果要求价值，这个价值和前一个物品有关，假如说现在的物品没有添加到背包里面，那么dp[i][j]=dp[i-1][j]，因为没有添加，所以价值的不便的，但是假如说现在的物品添加到背包里面了，那么dp[i][j]=dp[i-1][j-weight[i]]+value[i]，因为假如说添加了 ，那么肯定得留有weight[i]的容量才能让这个物品放下去，所以这时候前面的物品的背包容量应该是j-weight[i],那么在前面的基础上，就需要加上这个物品的价值，才是现在加入这个物品后的价值。

https://kamacoder.com/problempage.php?pid=1046

#include<iostream>
using namespace std;
#include<vector>
int n,bagweight;
void solve()
{
    vector<int>weight(n,0);
    vector<int>value(n,0);
    vector<vector<int>>dp(n,vector<int>(bagweight+1,0));
    for(int i=0;i<n;i++)
    {
        cin>>weight[i];
    }
    for(int j=0;j<n;j++)
    {
        cin>>value[j];
    }
    for(int j=weight[0];j<=bagweight;j++)
    {
        dp[0][j]=value[0];
    }
    for(int i=1;i<n;i++)
    {
        for(int j=1;j<=bagweight;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[n-1][bagweight]<<endl;
}
int main()
{
    while(cin>>n>>bagweight)
    {
        solve();
    }
    return 0;
}

滚动数组法

        滚动数组法就是把二维数组转换为一维数组，根据上面的讲解可以知道dp[i][j]其实只是跟dp[i-1][x](这里的x可能是j也可能是j-weight[i]),所以一维数组法就相当于每次在计算新的一行的时候，把上一行的结果搬到这一行，然后这一行再从后面向前面遍历更新值，为什么是从后往前遍历呢，因为dp[i][j]是跟之前的数值有关，假如说从前往后遍历，那么前面的值更新了，会导致后面的值在计算的时候用的dp[i-1][j]并不是原先的值（因为在前面遍历的时候前面的数值已经改变了，不再是我们直接搬下来的那些值）。

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

416.分割等和子集

https://leetcode.cn/problems/partition-equal-subset-sum/

        这道题神奇的点在于它居然也是动态规划的，我们把背包的容量看成是数的总和除以2，物品的价值看成是数的大小，问题就转化为了求背包容量为数的总和除以2的情况下，是否能够使得物品的最大价值等于数的总和除以2。

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