题目描述：给出一些不同面值的硬币，每个硬币只有一个。将这些硬币分成两堆，并且两堆硬币的面值和尽可能接近。
分析：将所有能够取到的面值数标记出来，然后选择最接近sum/2的两个面值
状态表示:d[j]表示用当前给定的硬币是否可以凑得总面值j
转移方程：d[j]=d[ j-coin[i] ]
开始时只取出硬币coin[0]，判断它是否能凑得总面值j
每新加入一个硬币coin[i]时，判断所有已经取出的硬币能否凑得总面值j
#include <iostream>
#include <cstdio>
#include <string.h>
#include <cmath>
#include <algorithm>
using namespace std; bool dp[];
int coin[];
int n,sum;
int main()
{
int t,i,j;
scanf("%d",&t);
while( t--)
{
scanf("%d",&n);
sum =;
for( i=; i<n; i++)
{
scanf("%d",&coin[i]);
sum+= coin[i];
}
memset( dp,, sizeof( dp));
dp[]=;
for( i=; i<n; i++)
for( j=sum;j>=coin[i]; j--)
if( !dp[j]) dp[j] =dp[j-coin[i]];
for( i=sum/; i>=;i--)
if( dp[i])
{
printf("%d\n",sum-i-i);
break;
}
}
return ;
}