题目大意：有n(n <= 100)个硬币，每个硬币的面额为1到500分，现在让你将这些硬币分成俩份，使得这俩份的硬币总额的差最小。
0-1背包问题，计算出所用硬币的总额sum，平均值aver = floor(sum/2)，实际上是计算小于等于aver的最大可分配金额。dp[i][j]表示只处理前i个硬币并且总金额小于等于j的金额总数。状态转移方程：dp[i][j] = max(dp[i-1][j], dp[i-1][j-a[i]] + a[i])。
1 #include <cstdio> 2 #include <algorithm> 3 using namespace std; 4 5 int dp[110][25100]; 6 int a[110]; 7 int main() 8 { 9 #ifdef LOCAL 10 freopen("in", "r", stdin); 11 #endif 12 int T; 13 scanf("%d", &T); 14 while (T--) 15 { 16 int n; 17 scanf("%d", &n); 18 int sum = 0; 19 for (int i = 1; i <= n; i++) 20 { 21 scanf("%d", &a[i]); 22 sum += a[i]; 23 } 24 int aver = sum / 2; 25 for (int i = 0; i <= aver; i++) 26 dp[0][i] = 0; 27 for (int i = 1; i <= n; i++) 28 for (int j = 0; j <= aver; j++) 29 { 30 dp[i][j] = dp[i-1][j]; 31 if (j >= a[i]) 32 dp[i][j] = max(dp[i][j], dp[i-1][j-a[i]]+a[i]); 33 } 34 printf("%d ", sum - dp[n][aver]*2); 35 } 36 return 0; 37 } 38 39