题目描述：给出一些不同面值的硬币，每个硬币只有一个。将这些硬币分成两堆，并且两堆硬币的面值和尽可能接近。
分析：将所有能够取到的面值数标记出来，然后选择最接近sum/2的两个面值
状态表示:d[j]表示用当前给定的硬币是否可以凑得总面值j
转移方程：d[j]=d[ j-coin[i] ]
开始时只取出硬币coin[0]，判断它是否能凑得总面值j
每新加入一个硬币coin[i]时，判断所有已经取出的硬币能否凑得总面值j
1 #include <iostream> 2 #include <cstdio> 3 #include <string.h> 4 #include <cmath> 5 #include <algorithm> 6 using namespace std; 7 8 bool dp[50001]; 9 int coin[101]; 10 int n,sum; 11 int main() 12 { 13 int t,i,j; 14 scanf("%d",&t); 15 while( t--) 16 { 17 scanf("%d",&n); 18 sum =0; 19 for( i=0; i<n; i++) 20 { 21 scanf("%d",&coin[i]); 22 sum+= coin[i]; 23 } 24 memset( dp,0, sizeof( dp)); 25 dp[0]=1; 26 for( i=0; i<n; i++) 27 for( j=sum;j>=coin[i]; j--) 28 if( !dp[j]) dp[j] =dp[j-coin[i]]; 29 for( i=sum/2; i>=0;i--) 30 if( dp[i]) 31 { 32 printf("%d ",sum-i-i); 33 break; 34 } 35 } 36 return 0; 37 }