Problem P33. [算法课分支限界法]分割等和子集

动态规划，dp，即计算多加第i个数，可以达到的数值可以到多少。详细可见：https://leetcode.cn/problems/partition-equal-subset-sum/solution/fen-ge-deng-he-zi-ji-by-leetcode-solution/

#include<iostream>
#include<bits/stdc++.h>
#include<cstdio>
#include<string>

using namespace std;

int main()
{
    vector<int> nums;
    while(1) {
        int d;
        int ret = scanf("%d", &d);
        if (ret == EOF) {
            break;
        }
        nums.emplace_back(d);
    }
    int n = nums.size();
    if (n < 2) {
        cout << "false";
        return 0;
    }
    int sum = 0, maxNum = 0;
    for (auto& num : nums) {
        sum += num;
        maxNum = max(maxNum, num);
    }
    if (sum & 1) {
        cout << "false";
        return 0;
    }
    int target = sum/2;
    if (maxNum > target) {
        cout << "false";
        return 0;
    }
    vector<int> dp(target + 1, 0);
    dp[0] = true;
    for (int i = 0; i < n; i++) {
        int num = nums[i];
        for (int j = target; j >= num; --j) {
            dp[j] |= dp[j-num];
        }
    }
    if (dp[target] == 1) {
        cout << "true";
    } else {
        cout << "false";
    }
    return 0;
}