力扣刷题记录（17）LeetCode：416、1049

416. 分割等和子集

可以将该问题看成是一个背包问题。背包的容量就是nums数组和的一半。我们如果能够将背包装满就意味着可以将数组分割成两个元素和相等的子集。 

1.确定dp[i]的含义

        索引i表示背包的容量，dp[i]表示当前容量能够装载的最大值

2.确定动态转移方程

        对于nums的各个元素我们有取和不取两种选择，我们取这两种方案中较大的值

        dp[i]=max(dp[j],dp[ j-nums[i] ]+nums[i] );

3.确定遍历方式

        先正序遍历nums数值，再倒序遍历背包容量。这里为什么要倒序遍历背包容量？因为如果正序遍历可能会出现重复取值的情况，而在本题nums中的每个值只能取一次。

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        if(nums.size()==1)  return false;
        int sum=0;
        for(int i=0;i<nums.size();i++)
        {
            sum+=nums[i];
        }
        if(sum%2==1)    return false;
        int back=sum/2; //背包容量
        vector<int> dp(10000+1,0);
        
        for(int i=0;i<nums.size();i++)
        {
            for(int j=back;j>=nums[i];j--)
            {
                dp[j]=max(dp[j],dp[j-nums[i]]+nums[i]);
            }
        }
        if(dp[back]==back)  return true;
        return false;
    }
};

1049. 最后一块石头的重量 II

这题和上题类似，要把题目转换成背包问题。可以把石头尽可能地分成两等份，这样可以使两份石头相撞时等到最小的石头。这样的话问题就变成了01背包问题，背包的容量为总石头的一半。需要注意的是在遍历背包容积时还是要采用倒序遍历，目的是每个避免重复取某一块石头。

class Solution {
public:
    int lastStoneWeightII(vector<int>& stones) {
        int sum=0;
        for(int i=0;i<stones.size();i++)
        {
            sum+=stones[i];
        }
        int pack=sum/2;
        vector<int> dp(pack+1,0);
        for(int i=0;i<stones.size();i++)
        {
            //进入for循环的条件是背包剩余容量要大于石头体积
            for(int j=pack;j>=stones[i];j--)
            {
                dp[j]=max(dp[j],dp[j-stones[i]]+stones[i]);
            }
        }
        return sum-2*dp[pack];
    }
};