将问题转换成分组背包，每一组有上下两个，每一组中必须选则一个，上面的价值为0，下面的价值为1，求价值最小
因为要求上下两部分差值最小，只需从背包大小为总数 / 2 时往前枚举，找最小答案即可。
——代码
1 #include <cstdio> 2 #include <cstring> 3 #include <iostream> 4 #define N 100001 5 #define min(x, y) ((x) < (y) ? (x) : (y)) 6 #define max(x, y) ((x) > (y) ? (x) : (y)) 7 8 int n, m, tot, ans; 9 int a[N], b[N], f[N]; 10 11 inline int read() 12 { 13 int x = 0, f = 1; 14 char ch = getchar(); 15 for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = -1; 16 for(; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + ch - '0'; 17 return x * f; 18 } 19 20 int main() 21 { 22 int i, j, tmp; 23 n = read(); 24 memset(f, 127 / 3, sizeof(f)); 25 for(i = 1; i <= n; i++) 26 { 27 tot += a[i] = read(); 28 tot += b[i] = read(); 29 m += max(a[i], b[i]); 30 } 31 f[0] = 0; 32 for(i = 1; i <= n; i++) 33 for(j = m; j >= 0; j--) 34 { 35 tmp = 1e9; 36 if(j >= a[i]) tmp = min(tmp, f[j - a[i]]); 37 if(j >= b[i]) tmp = min(tmp, f[j - b[i]] + 1); 38 f[j] = tmp; 39 } 40 for(i = tot >> 1;;i--) 41 { 42 ans = min(f[i], f[tot - i]); 43 if(ans < 1e9) 44 { 45 printf("%d ", ans); 46 return 0; 47 } 48 } 49 }