解题思路:

  • 输入时记录数组和sumsum, 如果sum%20sum \% 2 \neq 0直接输出false
  • 否则令dpj01,(0jsum/2)dp_j(01背包),(0 \leq j \leq sum/2),表示处理第ii个数时,容量为jj的背包,问题变为使用i和上一轮的值是否能构成jj。 状态转移方程:
dpj=1,(j=vi or dpjvi0)dp_j = 1,(j = v_i\ or\ dp_{j-v_i} \neq 0)
  • 最后根据dpsum/2dp_{sum/2}的值是否为1输出truefalse
#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    ios::sync_with_stdio(false);
    cin>>n;
    vector<int> v(n+1);
    int sum = 0;
    for(int i = 1; i <= n; ++i){
        cin>>v[i];
        sum += v[i];
    }
    int flag = 1;
    if(sum % 2 != 0) flag = 0;
    else {
        vector<int> dp(sum/2+1);
        for(int i = 1; i <= n; ++i){
            for(int j = sum/2; j >= v[i]; --j){
                if(j == v[i] || dp[j-v[i]] != 0) dp[j] = 1;
                else dp[j] = 0;
            }

        }
        flag = dp[sum/2];
    }
    cout<<(flag? "true": "false")<<endl;


    return 0;
}