正式开始背包问题喽！
416. 分割等和子集
给你一个只包含正整数的非空数组 nums。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
本题是 01背包的应用类题目。如何转换为01背包问题？物品是什么，背包又是什么？
本题要求集合里能否出现总和为 sum / 2 的子集。背包的的最大容量为sum / 2，集合中的元素就是物品的重量和价值。01背包中，dp[j] 表示：容量为j的背包，所背的物品价值最大可以为dp[j]。01背包的递推公式为：dp[j] = max(dp[j], dp[j - weight[i]] + value[i])。如果使用一维dp数组，物品遍历的for循环放在外层，遍历背包的for循环放在内层，且内层for循环倒序遍历！
还需要再思考！

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

努力啊！