leetcode——第416题——分割等和子集

题目： 给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

class Solution {
/*
转化为 01背包问题：
确定以下问题：
* 1、背包的体积为 sum/2， 物品的个数就是 nums数组的个数，背包中的每一个元素不可以重复放入。
* 2、物品的价值就是 nums 数组中每个元素（物品）的大小
* 3、物品的重量就是 nums 数组中每个元素（物品）的大小
* 4、背包中要放入的 物品重量 为 元素的数值，价值 为 元素的数值
* 5、是否能分割成两个元素和相等的子集 转换为 当背包容量为 sum/2 时所装的物品的最大价值能否是 sum/2
* 6、如果 dp[i] == i  
  * 说明集合中的子集总和正好可以凑成总和 i，
  * 也就是背包容量 为 i 时，所装物品的最大价值为 i，
  * 也就是可以将这个数组分割成两个子集，使得两个子集的元素和相等，这正是我们要求的。

动态规划五部曲：
1、确定dp数组以及下标的含义
dp[j] 表示容量为j的背包，所背的物品价值最大可以为 dp[j]

2、确定递归公式
首先记着01背包的递推公式：dp[j] = max(dp[j], value[i] + dp[j - weight[i]])
将上式转换一下： dp[j] = max(dp[j], nums[i] + dp[j - nums[i]])

3、dp数组初始化
与 01背包一样，当j=0,也就是背包容量为0时，dp[0] = 0;
且本题中数组元素均为正整数，因此初始化为 0 是没问题的，如果有负数，那就需要初始化为负无穷

4、确定遍历顺序
先遍历物品，再遍历背包容量
因为 01背包的一维 dp 数组，遍历顺序是固定的，只能是先物品，再背包容量
*/

public:
    bool canPartition(vector<int>& nums) 
    {
       if(nums.size() < 2)  return false;

       // dp[j] 表示背包容量为 j 时所背的物品最大价值为 dp[j]

       int sum = 0;
       for(int i = 0; i < nums.size(); i++)
       {
           sum += nums[i];
       }
       if(sum % 2 != 0) return false;
       int target = sum / 2;
       
       // 法一：：
       // 题中说明了每个数组中的元素不会超过100，数组的大小不会超过200，且分成2组
       // 所以背包的最大容量为 100*200/2，因为要装的是 sum/2
       // 1、啊！！！这个！想不到
       // vector<int> dp(10001, 0);  
       // 法二：:
       vector<int> dp(target + 1, 0); 

       dp[0] = 0;
       for(int i = 0; i < nums.size(); i++)
       {
           // 2、这里从大到小，也就是倒序遍历，为了保证每一个元素不被重复放入
           for(int j = target; j >= nums[i]; j--)
           {
               dp[j] = max(dp[j], nums[i] + dp[j - nums[i]]);
               if(dp[j] == target)   return true;
           }
       } 
       // 3、想不到！！！
       
       return false;
    }
};