题目内容

P1776

多重背包模板

解题思路

裸的多重背包,考虑像完全背包那样将每个物品进行二进制拆分,然后当作 0-1 背包一样处理即可。(不用单调队列优化是因为我太菜了不会)

主要的核心就是如何进行二进制拆分,即把每个物品拆分为诸如 2^j 个物品,可以将处理每个物品的时间复杂度降到 log 级别。

之后就是常规 0-1 背包

#include <cstdio>

inline int max(int a,int b)
{
    return a>b?a:b;
}

const int maxn=1e5+10;
int totn,W,n,v[maxn],w[maxn],f[(int)4e4+10];

int main()
{
    totn=0;
    scanf("%d %d",&n,&W);
    register int vv,ww,m;
    for(int i=1;i<=n;i++)
    {
        scanf("%d %d %d",&vv,&ww,&m);
        for(int j=1;j<=m;j<<=1)
        {
            m-=j;
            v[++totn]=vv*j,w[totn]=ww*j;
        }
        if(m)
            v[++totn]=vv*m,w[totn]=ww*m;
    }
    for(int i=1;i<=totn;i++)
        for(int j=W;j>=w[i];j--)
            f[j]=max(f[j],f[j-w[i]]+v[i]);
    printf("%d\n",f[W]);
    return 0;
}
最后修改日期:2020年2月26日

作者

留言

撰写回覆或留言

发布留言必须填写的电子邮件地址不会公开。