题解 | 数组分组 0-1背包解决分组问题

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

bool canAchieveTarget(vector<int>& nums, int target) {
    if(nums.size()==0) return target==0;

    int sum_neg=0,sum_pos=0;
    for(int i:nums){
        if(i<0) sum_neg+=i;
        else sum_pos+=i;
    }
    if(target<sum_neg || target>sum_pos) return false;

    int offset=-sum_neg;
    int total=sum_pos+offset;

    vector<vector<bool>>DP(nums.size()+1,vector<bool>(total+1,false));
    // for(int i=0;i<=nums.size();i++)
    DP[0][offset]=true;
    for(int i=1;i<=nums.size();i++){
        for(int j=0;j<=total;j++){
            DP[i][j]=DP[i-1][j] || DP[i][j];
            if(j>=nums[i-1] && j-nums[i-1]<=total)
            DP[i][j]=DP[i-1][j-nums[i-1]]||DP[i][j];
        }
    }
    return DP[nums.size()][target+offset];
}

int main() {
    int n;
    cin >> n;
    vector<int> a;
    vector<int> b;
    vector<int> other;
    int num;
    for (int i = 0; i < n; i++) {
        cin >> num;
        if (num % 5 == 0) {
            a.push_back(num);
        } else if (num % 3 == 0) {
            b.push_back(num);
        } else other.push_back(num);
    }
    int sum_a = 0, sum_b = 0, sum_other = 0;
    for (auto i : a) {
        sum_a += i;
    }
    for (auto i : b) {
        sum_b += i;
    }
    for (auto i : other) {
        sum_other += i;
    }
    int dis = abs(sum_a - sum_b);
    int target1, target2;
    int flag=(sum_other - dis) % 2;
    if (abs(flag) == 1) {
        cout << "false";
        return 0;
    }
    target1 = (sum_other - dis) / 2;
    target2 = target1 + dis;
    sort(other.begin(), other.end());
    if(canAchieveTarget(other, target1)){
        cout<<"true";
    }else cout<<"false";
}
    // for (int i = 0; i < )
    // }
// 64 位输出请用 printf("%lld")