hdu 1171 多重背包

题意：给出价值和数量，求能分开的最近的两个总价值，例如10,20*2,30，分开就是40，40
链接：点我
 1 #include<cstdio>
 2 #include<iostream>
 3 #include<algorithm>
 4 #include<cstring>
 5 #include<cmath>
 6 #include<queue>
 7 #include<map>
 8 using namespace std;
 9 #define MOD 1000000007
10 const int INF=0x3f3f3f3f;
11 const double eps=1e-5;
12 typedef long long ll;
13 #define cl(a) memset(a,0,sizeof(a))
14 #define ts printf("*****
");
15 const int MAXN=250010;
16 int n,m,tt;
17 int a[MAXN],b[MAXN];
18 int dp[MAXN];
19 
20 int nValue;
21 //0-1背包，代价为cost,获得的价值为weight
22 void ZeroOnePack(int cost,int weight)
23 {
24     for(int i=nValue;i>=cost;i--)
25         dp[i]=max(dp[i],dp[i-cost]+weight);
26 }
27 //完全背包，代价为cost,获得的价值为weight
28 void CompletePack(int cost,int weight)
29 {
30     for(int i=cost;i<=nValue;i++)
31         dp[i]=max(dp[i],dp[i-cost]+weight);
32 }
33 //多重背包
34 void MultiplePack(int cost,int weight,int amount)
35 {
36     if(cost*amount>=nValue)CompletePack(cost,weight);
37     else
38     {
39         int k=1;
40         while(k<amount)
41         {
42             ZeroOnePack(k*cost,k*weight);
43             amount-=k;
44             k<<=1;
45         }
46         ZeroOnePack(amount*cost,amount*weight);
47     }
48 }
49 int main()
50 {
51     int i,j,k;
52     #ifndef ONLINE_JUDGE
53     freopen("1.in","r",stdin);
54     #endif
55     while(scanf("%d",&n)!=EOF)
56     {
57         if(n<0) break;
58         nValue=0;
59         for(i=0;i<n;i++)
60         {
61             scanf("%d%d",&a[i],&b[i]);
62             nValue+=a[i]*b[i];
63         }
64         cl(dp);
65         for(i=0;i<n;i++)
66         {
67             MultiplePack(a[i],a[i],b[i]);
68         }
69         int v=nValue/2;
70         while(dp[v]!=v) v--;
71         printf("%d %d
",nValue-v,v);
72     }
73 }