【算法训练营day42】01背包问题基础 LeetCode416. 分割等和子集

LeetCode416. 分割等和子集

题目链接：416. 分割等和子集

独上高楼，望尽天涯路

一开始没有想到怎么转化成01背包问题，所以直接看题解找思路

慕然回首，灯火阑珊处

• 背包的体积为sum / 2
• 背包要放入的商品（集合里的元素）重量为 元素的数值，价值也为元素的数值
• 背包如果正好装满，说明找到了总和为 sum / 2 的子集。
• 背包中每一个元素是不可重复放入。

其中“价值也为元素的数值”是很巧妙的转化，我们的目标是找出使背包装满的组合，将价值设置为物品重量的大小（元素的数值）就可以保证遍历过程不断逼近装满这个目标，如果最后没有装满说明不存在这样的组合。

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        if (nums.size() == 1) {
            return false;
        }
        int sum_nums = 0;
        for (int num : nums) {
            sum_nums += num; 
        }
        if (sum_nums % 2 == 1) {
            return false;
        }

        int bag_weight = sum_nums / 2;
        vector<int> dp(bag_weight + 1, 0);
        for (int i = 0; i < nums.size(); i++) {
            for (int j = bag_weight; j >= nums[i]; j--) {
                dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);
            }
        }
        if (dp[bag_weight] == bag_weight) {
            return true;
        }
        else {
            return false;
        }
    }
};