Consider the partition problem: given a set S of n positive integers, partition it into two disjoint subsets S1 and S2 such that the discrepancy

                            E(S) = |sum(S1) - sum(S2)|

is minimized, where sum(Si) is the sum of Si's elements. Design an exhaustive search algorithm for this problem.
就是求2组数各自和的最小差的绝对值

/*

 * 将问题转换为求容量为sum/2的背包问题

 * 物体的重量为其具体值

 */

#include <stdio.h>

#define N sizeof(s) / sizeof(s[0])

int s[] = { 2, 5, 3, 1, 6, 4, 6, 7, 3, 4 };

int getSum()
{
    int sum = 0;

    for (int i = 0;i < N;i++)
    {
        sum += s[i];
    }
    return sum;
}

int fun(int n)
{
    int f[N + 1][n + 1];

    for (int i = 0;i <= N;i++)
    {
        for (int j = 0;j <= n;j++)
        {
            if (i == 0 || j == 0)
            {
                f[i][j] = 0;
                printf("%3d", f[i][j]);
                continue;
            }
            f[i][j] = f[i - 1][j];
            if (s[i - 1] <= j && f[i - 1][j - s[i - 1]] + s[i - 1] > f[i][j])
            {
                f[i][j] = f[i - 1][j - s[i - 1]] + s[i - 1];
            }
            printf("%3d", f[i][j]);
        }
        printf("\n");
    }

    return f[N][n];
}

int main(void)
{
    int sum = getSum();
    int max = fun(sum / 2);

    printf("max = %d\n", max);
    printf("ans = %d\n", sum - 2 * max);
    return 0;
}

噢噢，好的，谢谢，我一会试试。