zcmimi's blog

01背包

每个物品只能使用一次

普通多重背包

将可以用多次的物品拆为多个单次使用的物品

转化为01背包

二进制优化多重背包

但每个物品可以用的次数特别大的时候,如果还是直接拆很有可能会tle

LG 1776 宝物筛选

这时候可以使用二进制优化,

原理其实挺简单的:

比如7可以拆成1,2,4,用1,2,4可以凑出1-7中的任意一个数

根据这个原理,可以把物品拆成\log_2 \text{次数}个物品(价值和空间也跟着翻倍),降低时间复杂度

代码如下:

int n,W,tot=0,f[N];
struct node{int v,w;}a[N];
int main(){
    in(n,W);
    int v,w,m;
    for(int i=1;i<=n;++i){
        in(v,w,m);
        for(int t=1;t<=m;t<<=1)
            a[++tot]=node{v*t,w*t},
            m-=t;
        if(m)a[++tot]=node{v*m,w*m};
    }
    Fur(i,1,tot)
    for(int i=1;i<=tot;++i)
        for(int j=W;j>=a[i].w;--j)
            f[j]=max(f[j],f[j-a[i].w]+a[i].v);
    printf("%d\n",f[W]);
}

单调队列优化多重背包

还是这题LG 1776 宝物筛选

普通转移方程:

f(i,j)=max_{k\le m_i}\{f(i-1,j−kw)+kv\}

我们要将这个方程转化为可以单调队列优化的形式:

d=j \mod w_i,s=\left \lfloor \frac j{w_i}\right \rfloor,那么

f(i,j)=max_{s-k\le m_i}\{f(i-1,d+kw)-kv\}+vs

枚举d,对于每个d都用单调队列优化即可

代码如下:

#include<cstdio>
#include<algorithm>
using namespace std;
int n,V,ans,head,tail,q[40010],q2[40010],dp[40010];
int main(){
    scanf("%d%d",&n,&V);
    for(int i=1;i<=n;i++){
        int v,w,c;
        scanf("%d%d%d",&w,&v,&c);
        if(v==0){ans+=w*c;continue;}
        int k=V/v;
        c=min(c,k);
        for(int d=0;d<v;d++){
            head=tail=0;
            k=(V-d)/v;
            for(int j=0;j<=k;j++){
                while(head<tail&&dp[d+j*v]-j*w>=q2[tail-1])tail--;
                q[tail]=j;
                q2[tail++]=dp[d+j*v]-j*w;
                while(head<tail&&q[head]<j-c)++head;
                dp[d+j*v]=max(dp[d+j*v],q2[head]+j*w);
            }
        }
    }
    printf("%d",ans+dp[V]);
}
多重背包的优化
comment评论
Search
search