UVa 562: Dividing Coins

題意：給一串數字作為硬幣的幣值，將這些硬幣分給兩個人A和B，要求越平均越好。   假設總錢數為Sum且A分得的錢不超過B，開數組dp，dp[i]表示A是否可以分得一些硬幣使得其總錢數為i，dp[i]為1表示可以，0表示不可以。   dp數組初始化為0，dp[0]=1。然後分別對M個硬幣枚舉，判斷dp是否可置為1即可。最後選擇離Sum/2最近且dp[i]==1的i即可。   我的解題代碼如下：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>

using namespace std;
#define min(a,b) (a<b?a:b);
#define maxn 100
#define INF 50000  //可以優化：#define INF 25000
int Coin[maxn];
int dp[INF+5];
int main()
{
	int N,M,Sum;
	cin >> N;
	while(N--)
	{
		cin >> M;
		Sum = 0;
		for(int i=0; i<M; i++) { cin >> Coin[i]; Sum += Coin[i]; }
		memset(dp,0,sizeof(dp));
		dp[0] = 1;

		for(int i=0; i<M; i++)
		{
			for(int j=Sum-Coin[i]; j>=0; j--)  //可以優化：for(int j=Sum/2-Coin[i]; j>=0; j--) 因為我們最後只要比Sum/2小的i值
			{
				if(dp[j]) dp[j+Coin[i]] = 1;
			}
		}

		for(int i=Sum/2; i>=0; i--) if(dp[i])
		{
			cout << Sum-2*i << endl;
			break;
		}
	}
	return 0;
}