416. 分割等和子集 - 力扣（Leetcode）
给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
示例 1：
输入：nums = [1,5,11,5] 输出：true 解释：数组可以分割成 [1, 5, 5] 和 [11] 。
示例 2：
输入：nums = [1,2,3,5] 输出：false 解释：数组不能分割成两个元素和相等的子集。
提示：
1 <= nums.length <= 2001 <= nums[i] <= 100
题解思路
给出背包问题，大家都知道，有N件物品和一个最多能背重量为W 的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。
这道题目是要找是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。那么只要找到集合里能够出现 sum / 2 的子集总和，就算是可以分割成两个相同元素和子集了。
可以使用01背包来解题，元素不能重复取，所以使用01背包
首先需要确定以下几点：
- 有几个物品可供选择：
nums.size() - 背包的总容量是多少：
accumulate(nums.)/2
- 因为题目是要求出现两个子集，其和相等都为
sum/2
- 物品重量如何表示：
nums[i] - 物品价值如何表示：
nums[i]
动归五步：
二维dp
- 确定
dp数组及其含义
dp[i][j]代表从[0, i]中选择一件物品放入容量大小为j的背包所能获得的最大价值
- 确定递推公式
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - nums[i]] + nums[i])
这是01背包的标准格式，dp[i][j]可以由dp[i - 1][?]推出，取第i件物品与不取第i件物品两种取最大值
- 确定
dp数组的初始化
dp[0][0]同列初始化为0因为根据定义dp[i][0]代表从[0,i]中选择一件物品放入背包容量为0的背包中获得的最大价值，此处背包容量为0，所以第0列全部初始化为0，初始化第0行的时候也要根据定义，第0行代表就是选择第0件物品放入背包容量为j的背包中，所以只要背包装得下第0件物品，就初始化该位置为其价值
for(int i = nums[0]; i <= target; i++){ dp[0][i] = nums[0]; }
- 确定递推顺序
- 二维
dp数组遍历顺序很自由，我这里先顺序遍历物品，再顺序遍历容量
- 手动推导
dp数组
- 手写一下，看运行后是否与自己想的是否有区别来修改自己的代码
一维dp（滚动数组）
- 确定
dp数组及其含义
dp[j]表示容量为j的背包所能获得的最大价值，相较于二维dp数组，其就是将上一层复制到了下一层，因而后续递推公式是和自己比较
- 确定递推公式
dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);
- 确定
dp数组的初始化
dp[0]为背包容量为0，什么都装不了，肯定初始化为0，后续的值则dp数组在推导的时候一定是取价值最大的数，如果题目给的价值都是正整数那么非0下标都初始化为0就可以了。当然如果题目给出数组中有负数，则要初始化为INT_MIN来避免覆盖
- 确定递推顺序
- 首先给出代码
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]); } }
- 可以看见，与二维
dp相比，其遍历容量的时候是倒叙遍历的，这是为了保证保证物品i只被放入一次！。但如果一旦正序遍历了，那么物品0就会被重复加入多次！
换个说法：因为i每加1代表新的一行开始，由于dp[j-num[i]]每次都得使用的是上一行的数据。但是如果你正序的话，那么你在计算dp[j]的时候用到的dp[j-num[i]]是本行的，而不是上一行的，所以用逆序，逆序用到的dp[j-num[i]]是上一行的。
- 手动推导
dp数组
- 手写一下，看运行后是否与自己想的是否有区别来修改自己的代码
完整代码
class Solution { public: bool canPartition(vector<int>& nums) { // 有几个物品可供选择 -> nums.size() -> 用于i // 背包的总容量是多少 -> accumulate(nums.)/2 ->用于j // 物品重量如何表示 -> nums[i] -> weight[i] // 物品价值如何表示 -> nums[i] -> value[i] int sum = accumulate(nums.begin(), nums.end(), 0); if(sum % 2 == 1) return false; int target = sum / 2; // 一维数组 /*vector<int> dp(target + 1, 0); // 默认全体初始化为0 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; */ // 二维数组 vector<vector<int>> dp(nums.size(), vector<int>(target + 1, 0)); // 初始化 // dp[0][0]同列初始化为0 因为根据定义dp[i][0]代表从[0,i]中选择一件物品放入背包容量为0的背包中获得的最大价值，此处背包容量为0，所以第0列全部初始化为0，初始化第0行的时候也要根据定义，第0行代表就是选择第0件物品放入背包容量为j的背包中，所以只要背包装得下第0件物品，就初始化该位置为其价值 for(int i = nums[0]; i <= target; i++){ dp[0][i] = nums[0]; } for(int i = 1; i < nums.size(); i++){ for(int j = 1; j <= target; j++){ if(j < nums[i]) dp[i][j] = dp[i - 1][j]; else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - nums[i]] + nums[i]); } } if(dp[nums.size() - 1][target] == target) return true; return false; } };
