poj 1276 Cash Machine(多重背包)

题意：费用和价值相同的多重背包。

以前看背包的时候做过，今天又做了一遍。

二进制优化代码

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 using namespace std;
 5 
 6 int _max(int a,int b)
 7 {
 8     return a>b?a:b;
 9 }
10 
11 int d[100005];
12 int main()
13 {
14     int N,V,ni,C,W,c[15000],w[15000];//ni代表ni个物品，c是费用，w是价值
15     int count;
16     while(cin>>V>>N)
17     {
18         memset(d,0,sizeof(d));
19         count=1;
20         for(int i=1; i<=N; i++)
21         {
22             cin>>ni>>C;
23             W=C;
24             for(int j=1; j<=ni; j<<=1)
25             {
26                 c[count]=j*C;
27                 w[count++]=j*W;
28                 ni-=j;
29             }
30             if(ni>0)
31             {
32                c[count]=ni*C;
33                w[count++]=ni*W;
34             }
35         }
36         for(int i=1; i<count; i++)
37         for(int j=V; j>=c[i]; j--)
38         d[j]=_max(d[j],d[j-c[i]]+w[i]);
39 
40         cout<<d[V]<<endl;
41     }
42     return 0;
43 }