题解 | #农场的奶牛分组# 01背包

知识点

背包问题 DP

思路

首先先对所有的数求和，如果是奇数则不可拆分。

之后需要凑出sum/2的总和，问题转化成有n个数可以选一次或者不选，求出是否能凑出sum/2，则可以用01背包解决。

实现上可以一维空间优化。

时间复杂度 $O(n*sum)$

AC Code（C++）

#include <numeric>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param weights int整型vector 
     * @return bool布尔型
     */
    bool canPartition(vector<int>& weights) {
        int sum = accumulate(weights.begin(), weights.end(), 0);
        if (sum & 1) return false;
        sum >>= 1;
        vector<bool> f(sum + 1, false);
        f[0] = true;
        for (auto x : weights) {
            for (int j = sum; j >= x; j --) {
                f[j] = (f[j] || f[j - x]);
            }
        }
        return f[sum];
    }
};