题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1171
许多有价值的物品，有重复。问如何将他们分成两堆，使两堆价值之差最小。
对价值求和，转换成01背包，做一次，相当于一堆选物品使得最接近一半。然后这个结果和用价值和作差的结果就是两堆的价值，此时价值只差最小。
1 #include <algorithm> 2 #include <iostream> 3 #include <iomanip> 4 #include <cstring> 5 #include <climits> 6 #include <complex> 7 #include <fstream> 8 #include <cassert> 9 #include <cstdio> 10 #include <bitset> 11 #include <vector> 12 #include <deque> 13 #include <queue> 14 #include <stack> 15 #include <ctime> 16 #include <set> 17 #include <map> 18 #include <cmath> 19 20 using namespace std; 21 22 const int maxn = 555555; 23 int n; 24 int v[5555555]; 25 int m; 26 int dp[maxn]; 27 28 int main() { 29 // freopen("in", "r", stdin); 30 int vv, mm; 31 while(~scanf("%d", &n) && n >= 0) { 32 memset(dp, 0, sizeof(dp)); 33 memset(v, 0, sizeof(v)); 34 m = 1; 35 int half = 0; 36 for(int i = 0; i < n; i++) { 37 scanf("%d %d", &vv, &mm); 38 half += vv * mm; 39 while(mm--) v[m++] = vv; 40 } 41 for(int i = 1; i <= m; i++) { 42 for(int j = half / 2; j >= v[i]; j--) { 43 dp[j] = max(dp[j], dp[j-v[i]]+v[i]); 44 } 45 } 46 printf("%d %d ", half-dp[half/2], dp[half/2]); 47 } 48 return 0; 49 }