题意：给出n枚硬币，每个硬币有自己的面值，将这些硬币均分，有时无法均分，求分出来的两份硬币的最小差值
分析：统计总面值然后用总面值的一半作为背包容量，01背包。
代码：
View Code
1 #include <stdio.h> 2 #include <iostream> 3 #include <math.h> 4 #include <string.h> 5 using namespace std; 6 const int MAXN = 50000; 7 const int INF = 0x3f3f3f3f; 8 #define DEBUG 9 int c[MAXN]; 10 int dp[MAXN]; 11 int max(int a, int b){ 12 return a>b?a:b; 13 } 14 int main(){ 15 #ifndef DEBUG 16 freopen("in.txt", "r", stdin); 17 #endif 18 int n, m, i, j, k; 19 scanf("%d", &n); 20 for(i=0; i<n; i++){ 21 scanf("%d", &m); 22 int sum=0; 23 memset(dp, 0, sizeof(dp)); 24 for(j=1; j<=m; j++){ 25 scanf("%d", &c[j]); 26 sum+=c[j]; 27 } 28 int sum1 = sum/2; 29 for(j=1; j<=m; j++) 30 for(k=sum1; k>=c[j]; k--) 31 dp[k]=max(dp[k], dp[k-c[j]]+c[j]); 32 printf("%d\n", sum-2*dp[sum1]); 33 } 34 return 0; 35 }
