01背包模板、完全背包 and 多重背包（模板）

转载请注明出处：http://blog.csdn.net/u012860063

模版就直接贴代码：

01背包模板：

[cpp]view plain copy     
 print?
 /*    
 01背包问题    
 01背包问题的特点是，">每种物品仅有一件，可以选择放或不放。    
 01背包问题描述：    
 有N件物品和一个容量为V的背包。第i件物品的重量是c[i]，价值是w[i]。    
 求解将哪些物品装入背包可使这些物品的重量总和不超过背包容量，且价值总和最大。    
 */     
 #include <stdio.h>     
 #define N 1050017     
 int max(int x,int y)     
 {     
     int M;     
     M=x>y ? x : y;     
     return M;     
 }     
 int wei[N],val[N],f[N];     
 int main()     
 {     
     int i, j, n, m;     
     while(scanf("%d",&n)!=EOF)     
     {     
         scanf("%d", &m);     
         for(i=0; i<n; i++)     
             scanf("%d%d", &wei[i],&val[i]);//wei[i]为重量，val[i]为价值     
         for(i=0; i<n; i++)     
         {     
             for(j=m; j>=wei[i]; j--)     
                 f[j] = max(f[j], f[j-wei[i]]+val[i]);     
         }     
         printf("%d\n",f[m]);     
     }     
     return 0;     
 }     
      
 //此代码为poj3624    

完全背包模板：

[cpp]view plain copy     
 print?
 /*    
 完全背包问题的特点是，每种物品可以无限制的重复使用，可以选择放或不放。    
 完全背包问题描述：    
 有N物品和一个容量为V的背包。第i件物品的重量是wei[i]，价值是val[i]。    
 */     
      
 #include <cstdio>     
 #define INF 0x3fffffff     
 #define N 10047     
 int f[N],val[N],wei[N];     
 int min(int a,int b)     
 {     
     if(a < b)     
         return a;     
     return b;     
 }     
 int main()     
 {     
     int t,i,j,k,E,F,m,n;     
     scanf("%d",&t);     
     while(t--)     
     {     
         scanf("%d%d",&E,&F);     
         int c = F-E;     
         for(i = 0 ; i <= c ; i++)     
             f[i]=INF;     
         scanf("%d",&n);     
         for(i = 0 ; i < n ; i++)     
         {     
             scanf("%d%d",&val[i],&wei[i]);//val[i]为面额，wei[i]为重量     
         }     
         f[0]=0;//因为此处假设的是小猪储钱罐 恰好装满 的情况     
         //注意初始化（要求恰好装满背包，那么在初始化时除了f[0]为0其它f[1..V]均设为-∞，     
         //这样就可以保证最终得到的f[N]是一种恰好装满背包的最优解。     
         //如果并没有要求必须把背包装满，而是只希望价格尽量大，初始化时应该将f[0..V]全部设为0）     
         for(i =0 ; i < n ; i++)     
         {     
             for(j = wei[i] ; j <= c ; j++)     
             {     
                 f[j] = min(f[j],f[j-wei[i]]+val[i]);//此处求的是最坏的情况所以用min，确定最少的钱,当然最后就用max了，HEHE     
             }     
         }     
         if(f[c] == INF)     
             printf("This is impossible.\n");     
         else     
             printf("The minimum amount of money in the piggy-bank is %d.\n",f[c]);     
     }     
     return 0;     
 }     
 //此代码为HDU1114;    

f[w] 即为所求
初始化分两种情况：
1、如果背包要求正好装满则初始化 f[0] = 0, f[1~w] = -INF;

2、如果不需要正好装满 f[0~v] = 0;

多重背包模板：

[cpp]view plain copy     
 print?
 //多重背包(MultiplePack): 有N种物品和一个容量为V的背包。     
 //第i种物品最多有n[i]件可用，每件费用是c[i]，价值是w[i]。     
 //求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，     
 //且价值总和最大。     
 //HDU 2191     
      
 #include <cstdio>     
 #include <cstring>     
 #define N 247     
 int max(int a,int b)     
 {     
     if(a > b)     
         return a;     
     else return b;     
 }     
 int main()     
 {     
     int t,n,m,i,j,k;     
     int w[N],pri[N],num[N],f[N];     
     while(~scanf("%d",&t))     
     {     
         while(t--)     
         {     
             memset(f,0,sizeof(f));     
             scanf("%d%d",&n,&m);//n为总金额，m为大米种类     
             for(i = 0 ; i < m ; i++)     
             {     
                 scanf("%d%d%d",&pri[i],&w[i],&num[i]);//num[i]为每种大米的袋数     
             }     
             for(i = 0 ; i < m ; i++)     
             {     
                 for(k = 0 ; k < num[i] ; k++)     
                 {     
                     for(j = n ; j >= pri[i]; j--)     
                     {     
                         f[j] = max(f[j],f[j-pri[i]]+w[i]);     
                     }     
                 }     
             }     
             printf("%d\n",f[n]);     
         }     
     }     
     return 0;     
 }    