POJ 2576 二维背包

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<ctime>
 5 #include<algorithm>
 6 #include <map>
 7 #include <queue>
 8 using namespace std;
 9 const int maxn=57;
10 const int maxs=20500;
11 bool dp[maxn][maxs];
12 int weight[107];
13 int n;
14 int sum;
15 int slove()
16 {
17     memset(dp,0,sizeof(dp));
18     dp[0][0]=1;
19     int ans=0;
20     int nn=(n+1)>>1;
21     int sum2=sum>>1;
22     for(int k=1;k<=n;k++)
23     for(int i=nn;i>=1;i--)
24         for(int j=sum2;j>=weight[k];j--)
25 
26     {
27            if(!dp[i][j]) dp[i][j]=dp[i-1][j-weight[k]];
28            if(dp[i][j]&&j>ans) ans=j;
29     }
30 
31     return ans;
32 }
33 int main()
34 {
35     while(~scanf("%d",&n)){
36         sum=0;
37         for(int i=1;i<=n;i++)
38         {
39           scanf("%d",&weight[i]);
40           sum+=weight[i];
41         }
42         int ans=slove();
43         int ans2=sum-ans;
44         if(ans>ans2) swap(ans,ans2);
45         printf("%d %d\n",ans,ans2);
46     }
47 }