混合背包问题题目链接

7. 混合背包问题 - AcWing题库

混合背包问题题目类型

01背包模板+完全背包模板+多重背包问题模板

混合背包问题代码

#include<iostream>
#include<algorithm>

using namespace std;

const int N = 1010;

int n,m;
int f[N];
int main(){
    cin >> n >> m;
    for(int i=0;i<n;i++)
    {
        int v, w, s;
        cin>>v>>w>>s;
        if(s==0)
        {
            for(int j=v;j<=m;j++) f[j]=max(f[j],f[j-v]+w);
        }
        else
        {
            if(s==-1) s=1;
            for(int k=1;k<=s;k*=2)
            {
                for(int j=m;j>=k*v;j--)
                    f[j]=max(f[j],f[j-k*v]+k*w);
                s-=k;
            }
            if(s)
            {
                for(int j=m;j>=s*v;j--)
                    f[j]=max(f[j], f[j-s*v]+s*w);
            }
        }
    }
    cout<<f[m]<<endl;
    return 0;
}

二进制优化多重背包代码

#include<iostream>
#include<algorithm>

using namespace std;

const int V = 1010;

int f[V];

int main(){
    int n, m;
    scanf("%d%d", &n, &m);
    for(int i=0;i<n;++i)
    {
        int v,w,s;
        scanf("%d%d%d",&v,&w,&s);
        if(!s)
        {
            for(int j=v;j<=m;++j)
            {
                f[j]=max(f[j],f[j-v]+w);
            }
        }
        else if(s==-1)
        {
            for(int j=m;j>=v;--j)
            {
                f[j]=max(f[j],f[j-v]+w);
            }
        }
        else{
            for(int j=1;j<=s;j*=2)
            {
                for(int k=m;k>=j*v;k--)
                {
                    f[k]=max(f[k],f[k-j*v]+j*w);
                }
                s=s-j;
            }
            if(s)
            {
                for(int k=m;k>=s*v;k--)
                {
                    f[k]=max(f[k],f[k-s*v]+s*w);
                }
            }
        }
    }
    printf("%d\n",f[m]);
}