c++题解

#include<bits/stdc++.h>
using namespace std;

const int N = 505;
int a[N];


int main(){
    int n, sum = 0; cin >> n;
    for (int i = 0; i < n; i++){
        cin>>a[i];
        sum += a[i];
    } 
    
    
    if (sum&1){
        cout << "false"<<endl;
        return 0;
    }
    int target = sum/2;
    vector<int> dp(target+1, 0);
    for (int i = 0; i < n; i++){
        for (int j = target; j>=a[i]; j--){
            dp[j] = max(dp[j], dp[j-a[i]]+a[i]); 
        }
    }
    if (dp[target] == target) cout<<"true"<<endl;
    else cout<<"false"<<endl;
}