本文共 5157 字，大约阅读时间需要 17 分钟。

本篇文章以为基础，在阅读本篇文章之前，最好先看一下。

上一篇文章介绍了01背包问题，接下来我将介绍01背包的扩展问题：多重背包、完全背包以及混合背包。

1. 多重背包：

和01背包相比，多重背包只是在01背包的基础上多了一个物品数量s，那么解题的方法也很简单，要么把物品数量大于1的物品重复存入数组，要么在进行物品选择的时候多进行s-1次同一物品选择。看代码：

#include 
   
    using namespace std;int main(){    int n,m,i,j,k;    int v[505],w[505],s[505],dp[6005];    scanf("%d%d",&n,&m);    for(i=1;i<=n;i++) scanf("%d%d%d",&v[i],&w[i],&s[i]);    for(i=1;i<=n;i++)        for(j=1;j<=s[i];j++)        //多进行s[i]-1次判断            for(k=m;k>=v[i];k--)                dp[k]=max(dp[k],dp[k-v[i]]+w[i]);    printf("%d\n",dp[m]);}
   

#include 
   
    using namespace std;int v[5010],w[5010],dp[10000];int main(){    int n,m,t1,t2,t3;    cin>>n>>m;    int p=0;    for(int i=1;i<=n;i++)    {      cin>>t1>>t2>>t3;      for(int j=1;j<=t3;j++)    //将物品重复存入数组      {         v[++p]=t1;         w[p]=t2;      }    }    for(int i=1;i<=p;i++)      for(int j=m;j>=v[i];j--)       dp[j]=max(dp[j],dp[j-v[i]]+w[i]);    cout<
    
     <
    
   

其实本题的代码还可以进行优化，因为在实际比赛过程中，物品数量c[i]可能会比较大，按照上述两种方法很有可能超时。优化的方法就是对物品数量进行二进制分割。如18个物品，可以分割为1,2,4,8,3。为什么能进行这样的分割呢，因为每一个数都可以用一个唯一的二进制形式来表示，如上例，你会发现1-15都可以用1,2,4,8进行不同组合来表示，这自然不用说，而对于二进制分割后剩下来的那部分(即3)，同样也可以与1,2,4,8组合表示15-18的数，因为之前所有数的组合既然可以表示1-15的数，那么后面的15-18就可由(15-3)+3~15+3来表示，如16就可以表示为13+3。一般化一下，就是设一个数为n, 二进制分割后剩下x，那么除去x，前面部分可以表示1~(n-x)的数，那么后面(n-x+1)~n的数就可以由(n-x-x)+x~(n-x)+x来表示。关于装背包时的合理性，我们可以假设要使背包内物品价值最大要装n个某物品，那么由上述可知n可由上述二进制分割后的数组合表示，那么在打表的过程中，就可以不断通过选择组合找到n。看代码：while语句部分进行的就是分割操作。

#include 
   
    using namespace std;const int N=1e5+5;int v[N],w[N],dp[N];//v[n]价值 w[n]重量int main(){    ios::sync_with_stdio(false);    int n1,v1,x,vi,wi;    int p=0;    cin>>n1>>v1;    for(int i=1;i<=n1;i++)    {        cin>>wi>>vi>>x;        int c=1;        while(x-c>0)        {          x=x-c;          v[++p]=c*vi;          w[p]=c*wi;          c=c*2;        }        v[++p]=x*vi;        w[p]=x*wi;    }    for(int i=1;i<=p;i++)        for(int j=v1;j>=w[i];j--)    {       dp[j]=max(dp[j],dp[j-w[i]]+v[i]);    }    cout <
    
     << endl;    return 0;}
    
   

2. 完全背包：

和01背包和多重相比，完全背包的不同就是物品数量不限。在01背包中讲过，打表过程中背包容量要从最大值开始，为的是防止覆盖前一次生成的结果。而完全背包则相反，打表过程中要从w[i]开始，一直到最大背包容量，因为我们要的是在背包容量不断扩展的情况下，能装的最大价值(因为物品数量是无限的，所以在背包容量扩展时一个物品可能装多次)，要的就是这种覆盖。看代码：

#include 
   
    using namespace std;int main(){    int i,j;    int m,n;    int dp[205],w[35],c[35];    memset(dp,0,sizeof(dp));    scanf("%d%d",&m,&n);    for(i=1;i<=n;i++) scanf("%d%d",&w[i],&c[i]);    for(i=1;i<=n;i++)    {        for(j=w[i];j<=m;j++)        {            dp[j]=max(dp[j],dp[j-w[i]]+c[i]);        }    }    printf("max=%d\n",dp[m]);}
   

3. 混合背包：

混合背包就是多重背包和完全背包的结合体，在输入的时候，建个数组储存一下该组是完全背包还是多重背包，对于多重背包部分，进行二进制分割储存，完全背包部分直接储存，然后打表的时候对完全背包和多重背包分别进行操作就可以啦。看代码：

#include 
   
    using namespace std;int main(){    int i,j,p,n2;    int v,n;    int x,y,t;    int w[500],c[500],flag[500],dp[205];    memset(dp,0,sizeof(dp));    p=0;    scanf("%d%d",&v,&n);    for(i=1;i<=n;i++)    {        scanf("%d%d%d",&x,&y,&t);        if(t==0)        {            w[++p]=x;            c[p]=y;            flag[p]=0;        }        else        {            n2=1;            while(t-n2>0)            {                t-=n2;                w[++p]=n2*x;                c[p]=n2*y;                flag[p]=1;                n2*=2;            }            w[++p]=t*x;            c[p]=t*y;            flag[p]=1;        }    }    for(i=1;i<=p;i++)    {        if(flag[i]==0)        {            for(j=w[i];j<=v;j++)            dp[j]=max(dp[j],dp[j-w[i]]+c[i]);        }        else        {            for(j=v;j>=w[i];j--)            dp[j]=max(dp[j],dp[j-w[i]]+c[i]);        }    }    printf("%d\n",dp[v]);}
   

4. 最后来看两道扩展题：

樱花：

一样的是混合背包，不过值得一提的是算分钟数的方法。

#include 
   
    using namespace std;const int N=1e6+5;int t[N],c[N],flag[N],dp[N];int main(){    int i,j;    int h1,m1,h2,m2,n;    int x,y,tmp;    int p,v;    memset(dp,0,sizeof(dp));    p=0;    scanf("%d:%d%d:%d%d",&h1,&m1,&h2,&m2,&n);    v=(h2-h1)*60+(m2-m1);    for(i=1;i<=n;i++)    {        scanf("%d%d%d",&x,&y,&tmp);        if(tmp==0)        {            t[++p]=x;            c[p]=y;            flag[p]=0;        }        else        {            int n2=1;            while(tmp-n2>0)            {                t[++p]=x*n2;                c[p]=y*n2;                flag[p]=1;                tmp-=n2;                n2*=2;            }            t[++p]=tmp*x;            c[p]=tmp*y;            flag[p]=1;        }    }    for(i=1;i<=p;i++)    {        if(flag[i]==0)            for(j=t[i];j<=v;j++)                dp[j]=max(dp[j],dp[j-t[i]]+c[i]);        else            for(j=v;j>=t[i];j--)                dp[j]=max(dp[j],dp[j-t[i]]+c[i]);    }    printf("%d\n",dp[v]);}
   

买干草：

这道题就比较与众不同了，完全背包，但求的是最小值。因为是至少买h磅的干草包，所以可能出现买了某个干草包，总重量超出h磅，但花销变小的情况，因此dp[h]可能不是答案。因为单个干草包的重量小于等于5000，所以我们把h+5000即可。

#include 
   
    using namespace std;int main(){    int i,j;    int n,h;    int p[105],c[105],dp[55005];    scanf("%d%d",&n,&h);    for(i=1;i<=h+5000;i++) dp[i]=0x3f3f3f;    for(i=1;i<=n;i++)        scanf("%d%d",&p[i],&c[i]);    for(i=1;i<=n;i++)    {        for(j=p[i];j<=h+5000;j++)            dp[j]=min(dp[j],dp[j-p[i]]+c[i]);    }    int minn=0x3f3f3f;    for(i=h;i<=h+5000;i++) minn=min(minn,dp[i]);    printf("%d\n",minn);}