10
15
2015
0

多重背包单调队列优化的理解

其实我早就会写多重背包了……只不过是写成做多次01背包而已……

看着大爷秒题,我心中感到自己好弱啊。

于是我就来理解一下多重背包的单调队列做法,并记录在这里。

对于一个物品有个数限制的背包,我们考虑状态转移方程:

f[now][j]=max(f[last][j],f[last][j-w[i]*k]+c[i]*k),其中w[i]为重量,c[i]为价值。

感觉要枚举i,j,k,然后时间复杂度就爆炸了……

怎么办?用单调队列!

因为当我们取到了最大的f[last][j-w[i]*k]+c[i]*k时,再往下取k就没有意义了(不可能大于这个值)

所以我们维护一个单调队列,使队首为最大值,每次把不符合的队首删去,同时把队尾小于我们枚举的f[last][j-w[i]*k]+c[i]*k删去。

队列中存的是k,也就是记录当前取了多少个该物品,即可。

下面是一道例题。

----------------------------------------------------------------

超市购物

Description

Bob家附近新开了一家超市。最近,超市开展了促销活动。
超 市共出售N种不同的商品,编号为1…N。不同的物品对Bob来说有不同的价值,第i种物品每一个的价值为Wi。而每种商品的售价也不相同,第i种物品的单 价为Ci元。同一种商品可以买多个。超市经理为了避免某些商品被一抢而光,决定每种商品每位顾客最多只能买Li个。现在,Bob共有M元,他想知道在花费 不超过M元的情况下,能买到的商品价值和最大为多少?

Input

第1行两个整数N和M,分别表示商品的种数与Bob现有的钱数。
接下来N行每行为三个整数Ci,Wi,Li,分别表示第i种商品的单价,单个的价值,最多可购买的件数。

Output

输出只有一行,为Bob能买到的商品最大价值和。

Sample Input

5 30
3 1 3
1 4 1
8 10 3
4 7 2
2 2 4

Sample Output

42

Hint

20%的数据:N≤30,M≤10000,Li≤500;
70%的数据:N≤50,M≤500000,Li≤2000;
100%的数据:N≤50,M≤500000,Li≤500000;
----------------------------------------------------------------
Code:
#include<cstdio>
#include<algorithm>
using namespace std;

int n,m,l[55],c[55],w[55],f[2][500005],q[500005];

int main(){
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++){
    scanf("%d %d %d",&c[i],&w[i],&l[i]);
}
for(int i=1;i<=n;i++){
    int now=i%2,last;
    last=now^1;
    for(int j=0;j<c[i];j++){
        int Rear=1,Front=1;
        q[1]=0;
        for(int k=0;k*c[i]+j<=m;k++){
            while(Front!=Rear && k-q[Front]>l[i])Front++;
            f[now][k*c[i]+j]=max(f[last][k*c[i]+j],f[last][q[Front]*c[i]+j]+w[i]*(k-q[Front]));
            while(Front<=Rear && f[last][q[Rear]*c[i]+j]+w[i]*(k-q[Rear])<=f[last][k*c[i]+j])Rear--;
            q[++Rear]=k;
        }
    }
}
printf("%d\n",f[n%2][m]);
return 0;
}

 

Category: OI | Tags: OI | Read Count: 815

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com