UVA - 562 Dividing coins 经典01背包

题目大意：给出一系列硬币，要求分给两个人，且两个人得到的硬币差达到最小值

解题思路：用d[i]表示i这个数是否能被表示，则如果d[i - num[j]] == 1的话，num［j］表示硬币的价值，则d[i]就可以被表示，最后只要判断sum>>1然后递减到0的期间遇到哪个数字能表示的，能表示的话就找到结果了，结果为sum-2＊i，具体看代码，语言表达不太好，请见谅

#include<cstdio>
#include<cstring>
const int maxn = 100 + 5;
int m, dp[maxn*500],a[maxn];
int num;

int main() {
	int test;
	scanf("%d", &test);
	while(test--) {
		scanf("%d", &num);
		int sum = 0;
		memset(dp,0,sizeof(dp));
		dp[0] = 1;
		for(int i = 1; i <= num; i++)  {
			scanf("%d", &a[i]);
			sum += a[i];
		}

		for(int i = 1; i <= num; i++)
			for(int j = sum ; j - a[i] >= 0; j--)
				if(dp[j-a[i]]) 
					dp[j] = 1;
		for(int i = sum >> 1; i >= 0; i--) 
			if(dp[i]) {
				printf("%d\n",sum-i*2);
				break;
			}	
	}
	return 0;
}