n个数，要求尽量均分的问题

问题：

现在有n个数，要求你把它分为两部分，而且尽量均分，即两部分和的差值最小。

解决：

设n个数的总和是sum，mid = sum/2，那么这个问题可以转化成从n个数中，选取几个数使它们的和尽量接近mid 。我们可以建立一个大小为 mid 的背包，看背包最大能装多少东西，求出来的最大值就是可以组合出来的最接近 mid 的数。

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

int dp[11000];
int a[110];
int n;

void solve(){
    int sum=0;
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        scanf("%d",&a[i]);
        sum+=a[i];
    }
    int mid=sum/2;
    for(int i=0;i<n;i++){
        for(int j=mid;j>=a[i];j--){
            dp[j]=max(dp[j],dp[j-a[i]]+a[i]);
        }
    }
    printf("%d %d\n",dp[mid],sum-dp[mid]);
}

int main(){
    solve();
    return 0;
}