背包模板

 1 //每件物品只能使用一次
 2 void onezeropack(int v,int c)
 3 {
 4     int j;
 5     for(j=val; j>=v; j--)
 6     {
 7         f[j]=max(f[j-v]+c,f[j]);
 8     }
 9 }
10 //每件物品可以无限使用
11 void completepack(int v,int c)
12 {
13     int j;
14     for(j=v; j<=val; j++)
15     {
16         f[j]=max(f[j-v]+c,f[j]);
17     }
18 }
19 //每件物品有限次使用
20 void multiplepack(int v,int c,int num)
21 {
22     if(v*num>=val)
23     {
24         completepack(v,c);
25         return;
26     }
27     int k=1;
28     while(k<num)
29     {
30         onezeropack(k*v,k*c);
31         num=num-k;
32         k=k*2;
33     }
34     onezeropack(num*v,num*c);
35 }

注意：背包的第一重循环要自己写

for(int i = 0 ;i < n ; i++)　　

调用其中一个函数

f[N]为dp数组

 1 #define N 100005  
 2 int m,f[N];  
 3 int Max(int a,int b)  
 4 {  
 5     return a>b?a:b;  
 6 }  
 7 void Zeroone(int c,int w)          // 01背包  
 8 {  
 9     int i;  
10     for(i=m;i>=c;i--)  
11         f[i]=Max(f[i],f[i-c]+w);  
12 }  
13 void Comple(int c,int w)       //完全背包  
14 {  
15     int i;  
16     for(i=c;i<=m;i++)  
17         f[i]=Max(f[i],f[i-c]+w);  
18 }  
19 void Multi(int c,int w,int num)     //多重背包  
20 {  
21     if(c*num>=m)  
22         Comple(c,w);  
23     else  
24     {  
25         int i=1;           //二进制思想，用一些数表示所有可能的组合。  
26         while(i<num)  
27         {  
28             Zeroone(i*c,i*w);  //如num=13，可以用1，2,4,6表示所有组合  
29             num-=i;  
30             i*=2;  
31         }  
32         Zeroone(c*num,w*num);  
33     }  
34 }