分类
OI

初学DP(4) – 多重背包及其优化 – Codevs 3269

多重背包 我们曾经说过完全背包和01背包,但是这两个方法都有一个问题,就是物件个数都是一致的并且是确定的,但如果他不确定呢? 我们可以定义一个k循环来模拟他的件数,不过显然这样做的华时间复杂度会超过我们的想象 所以我们需要进行优化,优化的方式有两种

  • 二进制优化
  • 单调队列

二进制优化


我们来观察下面这几个数字 十进制 1 2 4 8 二进制 1 10 100 100 我们可以发现这几个数每次乘二,并且可以凑成从 1 到 1+2+4+8=15 的所有情况 至于是什么原因可以观察一下二进制数 1+10=11(3) 1-3凑齐 11+1=100(4) 1-3,4,5-7凑齐 没错每个为2^n的数,它的二进制中,第一位是1,后面全是0,这样一来我们只需要把是2^n次放并且和小于个数的数求出来,之后按个数相乘成为一个新的物品

单调队列


是否还记得队列呢? 单调队列也是队列,所谓的单调,就是指按队列中的顺序 是固定的,也就是指最优解永远放在最前面,但是问题来了,阶段不同的最优解改怎么办呢? 我们来推导一下
k=1
f[1] max( f[1]-1*w+1*w)
k=1
f[2] max(f[2]-2*w+2*w,f[1]-1*w+2*w)
k=1
f[3] max(f[3]-3*w+3*w,f[2]-2*w+3*w,f[1]-1*w+3*w)
于是我们发现
f[k]=f[k]-kw+kw f[n]=f[n]-nw+kw
所以我们可以对队列进行维护,所有存在队列里的值去掉 k*w 的部分

混合背包

题目链接: [http://codevs.cn/problem/3269/]
很裸的模板题了,我们直接开始写吧

二进制优化

时间: 4316 ms 内存: 1004 kb
#include <cstdio>
using namespace std;
int z,cnt,m;// 二进制拆分用
int n,V;// n 物品数量 V 体积
int v[10100000],w[10100000],alen;// v[] 体积 w[]价格 alen 长度
int f[10100000];// f[] 动归专用
int main(){
//读入
    scanf("%d%d",&n,&V);
    for(int i=1;i<=n;i++){
        scanf("%d%d%d",&v[alen],&w[alen],&m);
  z=alen;// 将 z 保留住
        alen++;
        if(m==-1) m=V/v[z]; //如果为无限的话,就按能放下的最大值走
        cnt=m-1;//-1是因为已经有 1 了
       //开始拆分
  for(int j=2;;j*=2){
            if(cnt>j){//如果还能拆,继续插并增加物品件数
                cnt-=j;
                v[alen]=v[z]*j;
                w[alen]=w[z]*j;
                alen++;
            }
            else {
                v[alen]=v[z]*cnt;
                w[alen]=w[z]*cnt;
                alen++;
                break;
            }
        }
    }
// dp[] 二进制拆分玩就是一个 01 背包了
    for(int i=0;i<alen;i++){
        for(int j=V;j>=v[i];j--){
            if(f[ j-v[i] ]+w[i]>f[j]){
                f[j]=f[ j-v[i] ]+w[i];
            }
        }
    }
    printf("%d",f[V]);
}

单调队列

时间: 2430 ms 内存: 2 MB
#include <cstdio>
#include <iostream>
using namespace std;
int n,V,v,w,m;
int f[210000];// dp[]
struct node {
    int f,id;
}q[210000];
int l,r;
int main(){
    scanf("%d%d",&n,&V);
    for(int i=1;i<=n;i++){
        scanf("%d%d%d",&v,&w,&m);
        if(m==-1||m*v>V) m=V/v;
        for(int j=0;j<v;j++){
            l=r=0;
            for(int k=j,id=0;k<=V;k+=v,id++){
                while(l!=r&&q[r-1].f<=f[k]-id*w) r--;// 如果队尾解不如当前解就去掉
                q[r++]=node{f[k]-id*w,id};
                while(l!=r&&id-q[l].id>m) l++;// 如果目前所有的所有数量也达不到队首要求也去掉
                f[k]=q[l].f+id*w;
            }
        }
    }
    printf("%d",f[V]);
}

极限优化


时间: 1952 ms 内存: 2 Mb
#include <cstdio>
#include <iostream>
using namespace std;
int n,V,v,w,m;
int f[210000];
struct node {
    int f,id;
}q[210000];
int l,r;
// 01背包
void oz(int v,int w){
    for(int i=V;i>=v;i--){
       f[i]=max(f[i],f[i-v]+w);
    }
}
// 完全背包
void wq(int v,int w){
    for(int i=v;i<=V;i++){
       f[i]=max(f[i],f[i-v]+w);
    }
}
// 单调队列优化多重背包
void queueyh(int v,int w,int m){
    for(int j=0;j<v;j++){
        l=r=0;
        for(int k=j,id=0;k<=V;k+=v,id++){
            while(l!=r&&q[r-1].f<=f[k]-id*w) r--;
            q[r++]=node{f[k]-id*w,id};
            while(l!=r&&id-q[l].id>m) l++;
            f[k]=q[l].f+id*w;
        }
    }
}
int main(){
    scanf("%d%d",&n,&V);
    for(int i=1;i<=n;i++){
        scanf("%d%d%d",&v,&w,&m);
        if(m==-1||m*v>V) wq(v,w);// 如果m都放进来已经大于背包就可以直接用无限
        else if(m==1) oz(v,w);// 只有1个就交给01背包吧
        else queueyh(v,w,m);
    }
    printf("%d",f[V]);
}

END

多重背包实际上与前两中差别不大,不过重点在于优化,优化不得当直接TLE ]]>

发表评论

电子邮件地址不会被公开。 必填项已用*标注