C++实现【问题描述】 已知由n（n≥2）个正整数构成的集合A={ak}（0≤k<n），将其划分为两个不相交的子集A1和A2，元素个数分别是n1和n2， A1和A2中元素之和分别为S1和S2。设计一个划分算法，满足|n1-n2|最小且|S1-S2|最大。 【输入形式】 两行，第一行N，代表数组中共有N个元素 第二行，N个整数，逗号隔开 【输出形式】 两个数，逗号隔开，第一个数等于|n1-n2|，第二个数等于|S1-S2| 【样例输入】 例一 4 1,2,7,8 例二 5 1,2,5,7,8

以下是C++代码实现：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main(){
    int n;
    cin >> n;
    vector<int> a(n);
    int sum = 0;
    for(int i=0; i<n; i++){
        cin >> a[i];
        sum += a[i];
    }

    vector<vector<int>> dp(n+1, vector<int>(sum/2+1, 0));
    for(int i=1; i<=n; i++){
        for(int j=1; j<=sum/2; j++){
            if(a[i-1] > j){
                dp[i][j] = dp[i-1][j];
            }
            else{
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-a[i-1]]+a[i-1]);
            }
        }
    }

    int s1 = dp[n][sum/2];
    int s2 = sum - s1;
    int n1, n2;
    for(int i=n; i>=1; i--){
        if(s1 >= a[i-1] && dp[i-1][s1-a[i-1]] + a[i-1] == s1){
            n1 = i - 1;
            break;
        }
    }
    n2 = n - n1;
    cout << abs(n1 - n2) << "," << abs(s1 - s2) << endl;

    return 0;
}

输入样例：

4
1,2,7,8

输出样例：

1,8