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 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]));elsedp[i][j] = dp[i - 1][j];printf("%d\n", sum - dp[m][sum2] - dp[m][sum2]);}return 0;
}