其实我早就会写多重背包了……只不过是写成做多次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元的情况下，能买到的商品价值和最大为多少？
超 市共出售N种不同的商品，编号为1…N。不同的物品对Bob来说有不同的价值，第i种物品每一个的价值为Wi。而每种商品的售价也不相同，第i种物品的单 价为Ci元。同一种商品可以买多个。超市经理为了避免某些商品被一抢而光，决定每种商品每位顾客最多只能买Li个。现在，Bob共有M元，他想知道在花费 不超过M元的情况下，能买到的商品价值和最大为多少？
Input
第1行两个整数N和M，分别表示商品的种数与Bob现有的钱数。
接下来N行每行为三个整数Ci,Wi,Li，分别表示第i种商品的单价，单个的价值，最多可购买的件数。
接下来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
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；
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;
}
Sep 19, 2021 06:21:45 PM
Winters tend to be incomplete without having snuggling within the warm covers. Clean individuals soft covers and pillows before you decide to put all of them into make use of. Drop them within the washing device and clean them according to their manufacturers’ directions. If a person don’t would like the blankets to obtain dull, then toss a tennis games ball within the washing device before running force cycle. You can observe the difference since the feathers won’t stay together as well as won’t really feel lumpy, whatsoever.