力扣-416题 分割等和子集（C++）- 0-1背包

题目链接：https://leetcode.cn/problems/partition-equal-subset-sum/
题目如下：

class Solution {
public:
    bool canPartition(vector& nums) {
        int n=nums.size();//背包问题中物品的数量
        int sum=0;
        for(auto e:nums){
            sum+=e;
        }
        if(sum%2!=0) return false;
        sum/=2;//背包问题中背包的总容量

        //0-1背包问题：即每次只做一个决策，判断一个物品是否放入背包
        vector> dp(n,vector(sum+1,false));
        dp[0][0]=true;
        if(nums[0]<=sum) dp[0][nums[0]]=true;//在对第1次物品作决策时，分为放或者不放，上一行为不放入背包，这一行为放入

        for(int i=1;i//从第二件物品开始依次判断作决策
            for(int j=0;j<=sum;j++){
                if(j-nums[i]>=0){//当前背包的重量减去当前物品的重量可以判断出是否要将该物品放入背包
                    dp[i][j] = dp[i-1][j] || dp[i-1][j-nums[i]];//当前状态为上一个状态放或不放的组合
                }else{
                    dp[i][j]=dp[i-1][j];//当前物品不放入背包
                }
            }
        }

        return dp[n-1][sum];//表示在对所有n件物品决策完后，背包重量为sum时的判断
    }
};