给定一个数组，让给出一个算法，使得两个组的和的差的绝对值最小

数组中的数的取值范围是(0,100)，元素个数也是(0,100)，比如

a[5] = {2,4,5,6,7}, 得出两组数{2,4,6}和{5,7}， abs(sum(a1)-sum(a2)) = 0,

a[4] = {2,5,6,10}, 两组{2,10}, {5,6}, abs(sum(2,10)-sum(5,6)) = 1.

这一题曾在cdsh上讨论火热。乌拉尔大学oj上面有一题和这个差不多。

原题链接：http://acm.timus.ru/problem.aspx?space=1&num=1005

5
5 8 13 27 14

3

这一题实际上是个01背包，原问题等价于从n个物品中选取若干个，其重量不超过sum/2，且重量达到最大。

oj上这题因为数据规模小n<=20，所以也可以dfs，dfs话不会超过10^6级，所以时间上完全够用。但是面试题里边n最大100，只能用dp。

dfs方法：

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int M = 20 + 5;
const int INF = 0x3f3f3f3f;
int n, ans, sum;
int w[M];
void dfs(int i, int cursum) {
    if (i == n) {
        ans = min(ans, abs(sum-2*cursum));
        return;
    }
    dfs(i+1, cursum+w[i]);
    dfs(i+1, cursum);
}
int main()
{
    while (scanf("%d", &n) != EOF) {
        sum = 0;
        for (int i = 0; i < n; ++i) {
            scanf("%d", &w[i]);
            sum += w[i];
        }
        ans = INF;
        dfs(0, 0);
        printf("%dn", ans);
    }
    return 0;
}

#include <iostream>
#include <cstdio>
#include <cstring>                  //for memset 
#include <algorithm>                //for max
using namespace std;
const int M = 20 + 5;
int w[M];
int dp[M*100000];
int main()
{
    int n;
    while (scanf("%d", &n) != EOF) {
        int sum = 0;
        for (int i = 0; i < n; ++i) {
            scanf("%d", &w[i]);
            sum += w[i];
        }
        memset(dp, 0, sizeof(dp));
        for (int i = 0; i < n; ++i)
            for (int j = sum/2; j >= w[i]; --j)
                dp[j] = max(dp[j], dp[j-w[i]] + w[i]);
        printf("%dn", sum - dp[sum/2]*2);
    }
    return 0;
}

#include <iostream>
#include <cstdio>
#include <cstring>                  //for memset 
#include <algorithm>                //for max
using namespace std;
const int M = 100 + 10;
int w[M];
int dp[M*100];
bool state[M][M];
int main()
{
    int n;
    while (scanf("%d", &n) != EOF) {
        int sum = 0;
        for (int i = 0; i < n; ++i) {
            scanf("%d", &w[i]);
            sum += w[i];
        }
        memset(dp, 0, sizeof(dp));
        memset(state, 0, sizeof(state));
        for (int i = 0; i < n; ++i)
            for (int j = sum/2; j >= w[i]; --j) {
                if (dp[j] < dp[j-w[i]] + w[i]) {
                    dp[j] = dp[j-w[i]] + w[i];
                    state[i][j] = true;
                }
            }
        printf("%dn", sum - dp[sum/2]*2);
        int i = n, j = sum/2;
        while (i--) {
            if (state[i][j]) {
                printf("%d ", w[i]);
                j -= w[i];
            }
        }
        printf("n");
    }
    return 0;
}