题目描述：

n个人，每个人体重x[i]，让你把他们分成两组，两组之间的人数差不能大于1。输出两组体重差最小的情况。

解题报告：

dp

dp[i][101] = 1，表示体重和为i可以达到。

dp[i][j] = 1，表示j个人可以构成体重i.

然后看代码就明白了：

#include<iostream>
using namespace std;
#define size 45005
int n, x[103], sum, ans, l, r;
int aabs(int a, int b){ return a - b < 0 ? b - a : a - b;}
bool dp[size][103];
int main()
{
    memset(dp, 0, sizeof(dp));
    scanf("%d", &n);sum = 0;
    for(int i = 1; i <= n ;i )
    {
        scanf("%d", &x[i]);
        sum = x[i];
    }
    ans = 0;dp[0][0] = dp[0][101] = 1;
    for(int i = 1; i <= n ;i )
        for(int j = sum; j >= x[i]; j--)
            if (dp[j - x[i]][101])
            {
                dp[j][101] = 1;
                for(int k = 0; k < n; k )
                    if (dp[j - x[i]][k]) dp[j][k 1] = 1;
            }
    ans = 1000000000;
    for(int i = 0; i <= sum; i )
        if (dp[i][101] && (dp[i][n / 2] || dp[i][(n 1) / 2]))
            if (aabs(sum - i, i) < ans)
                ans = aabs(sum - i, i);
    ans = (sum - ans) / 2;
    printf("%d %d\n", ans, sum - ans);
    return 0;
}