POJ 2576 Tug of War二维背包恰好装满.

像这种恰好装满的情况可以用bool数组，恰好装满为true,否则为false。

还有就是逆向推倒，0-1背包，f[i][j]表示有i个人，组成了j的体重，这样的话在考虑某人的情形时，f[i][j]为真的前提就是f[i-1][j-wi]为真，其中wi为这个人的体重

View Code

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <cmath>
 4 bool f[110][2500];
 5 int main()
 6 {
 7     int n,w[110],sum = 0;
 8     scanf("%d\n",&n);
 9     memset(f,false,sizeof(f));
10     f[0][0] = true;
11     for(int i=0; i<n; i++)
12     {
13         scanf("%d",&w[i]);
14         sum += w[i];
15     }
16     int v = n/2;
17     for(int i=0; i< n; i++)
18     {
19         for(int j = v; j >= 0; j--)
20         {
21             for(int k=sum; k >= 0; k--)
22             {
23                 if( j >=1 && k>= w[i] &&f[j-1][k-w[i]])
24                     f[j][k] = true;
25             }
26         }
27     }
28     int mi1=0,mi2=sum;
29     double dif = sum;
30     for(int i=sum-1; i>=0; i--)
31     {
32         if(f[v][i] && dif>fabs(sum-2*i))
33         {
34             mi1 = i;
35             mi2 = sum-i;
36             dif = fabs(sum-2*i);
37         }
38     }
39     if(mi1 > mi2)
40         printf("%d %d\n",mi2,mi1);
41     else  printf("%d %d\n",mi1,mi2);
42     return 0;
43 }