UVALive5583 UVA562 Dividing coins

Regionals 1996 >> Europe - Northwestern

问题链接：UVALive5583 UVA562 Dividing coins。

问题简述：输入测试用例数n，每个测试用例包括金币的数量m和m个正整数是金币的币值。将这些金币分为两堆，使得其差值最小，求最小的差值。

问题分析：可以用0/1背包的动态规划方法来解决这个问题。将背包的容量设为所有金币币值之和的一半，将这一堆金币尽可能多地放入背包即可。再计算一下差值即可。

0/1背包动态规划法的递归式为f(j,X)，其中j=0,1,2,...,n-1为物品（共n个物品），X是背包的载重量。f(j,X)的含义为：当背包载重为X，可供选择的物品为0,1,2,...,j时的最优值。具体式子如下：

f(-1,X)＝-∞(X<0)，f(-1,X)=0(X>=0)

f(j,X)=max{f(j-1,X), f(j-1(X-wj)+pj} 0<=j<n，wj为第j件物品重量，pj为第j件物品收益。

程序说明：程序中，用二维数组dp[][]来存放递推函数的值，比较浪费存储空间，应该使用STL构筑一个稀疏矩阵来存储比较合理。

另外，wj＝coin[j]即币值，pj=coin[j]即币值，一种特例情况。程序逻辑实际上是套用0/1背包递推函数。

AC的C语言程序如下：

/* UVALive5583 UVA562 Dividing coins */

#include <stdio.h>
#include <memory.h>

#define MAX(x, y) (((x)>(y))?(x):(y))

#define MAXN 100

int dp[MAXN+1][MAXN * 500];

int main(void)
{
    int t, m, coin[MAXN+1], sum, sum2, i, j;

    scanf("%d", &t);
    while(t--) {
        scanf("%d", &m);

        memset(coin, 0, sizeof(coin));
        memset(dp, 0, sizeof(dp));

        sum = 0;
        for(i=1; i<=m; i++) {
            scanf("%d", &coin[i]);
            sum += coin[i];
        }


        sum2 = sum / 2;
        for(i=1; i<=m; i++)
            for(j=0; j<=sum2; j++)
                if(j >= coin[i])
                    dp[i][j] = MAX(dp[i - 1][j], (dp[i - 1][j - coin[i]] + coin[i]));
                else
                    dp[i][j] = dp[i - 1][j];

        printf("%d
", sum - dp[m][sum2] - dp[m][sum2]);
    }

    return 0;
}