题意：
将一个数组分成两堆，使两堆的和的差值尽可能小。
思路：
dp。
实现：
1 #include <bits/stdc++.h> 2 using namespace std; 3 4 int splitToMin(int a[], int n, int b[], int c[]) 5 { 6 int sum = accumulate(a, a + n, 0); 7 int dp[15][1005]; 8 memset(dp, 0, sizeof dp); 9 for (int i = 1; i <= n; i++) 10 { 11 for (int j = sum >> 1; j >= a[i - 1]; j--) 12 { 13 dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - a[i - 1]] + a[i - 1]); 14 } 15 } 16 int tot = dp[n][sum >> 1], ans[15]; 17 memset(ans, 0, sizeof ans); 18 for (int i = n; i >= 1; i--) 19 { 20 if (dp[i][tot] > dp[i - 1][tot]) 21 { 22 tot -= a[i - 1]; 23 ans[i - 1] = 1; 24 } 25 } 26 int x = 0, y = 0; 27 for (int i = 0; i < n; i++) 28 { 29 if (ans[i]) b[x++] = a[i]; 30 else c[y++] = a[i]; 31 } 32 return abs(sum - 2 * dp[n][sum >> 1]); 33 } 34 35 int main() 36 { 37 int a[] = {61, 82, 100, 61, 61}; 38 int b[10], c[10]; 39 memset(b, 0, sizeof b); memset(c, 0, sizeof c); 40 cout << splitToMin(a, 5, b, c) << endl; 41 for (int i = 0; i < 5; i++) cout << b[i] << " "; 42 cout << endl; 43 for (int i = 0; i < 5; i++) cout << c[i] << " "; 44 cout << endl; 45 return 0; 46 }