Regionals 1996 >> Europe - Northwestern

问题链接：。

问题简述：输入测试用例数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 
    
     #include 
     
      #define MAX(x, y) (((x)>(y))?(x):(y))#define MAXN 100int 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\n", sum - dp[m][sum2] - dp[m][sum2]);    }    return 0;}