多重背包问题：
有n件物品，第i件价值为wi,质量为vi,有c1件，问，给定容量V，求获得的最大价值。
朴素做法：
视为0,1,2，...,k种物品的分组背包 [每组只能选一个]
f[i][j]=Max(f[i][j-k*v[i]]+k*w[i])
但是i,j,k都要枚举，复杂度为 n*V*k
朴素做法的改进：
因为发现用二进制可以表示1..k之内的所有数 [整数二进制打开后为01串，所以可以被二进制表示]
所以将k个物品拆分成1,2,4...2^m,k-2^m ( 其中2^m<=k<2^(m+1) ) 这些物品，然后变成01背包问题。
但是n的数目增多了，复杂度为 n*V*logk
利用单调队列的改进：
1.我们可以发现每个容量都能表示成 v*x+d 的形式[ v表示当前考虑的物品的容量 ]
2.在上一点的启发下，我们发现一个f[v*x+d]在考虑当前物品时，只能由f[v*y+d]转移而来。 [其中x-y<=k]。
也就是说，对v取模的余数相同的容量之间才能互相转移，而且要求x-y<=k。又因为求的是最大值的转移，所以满足单调队列的适用性。
于是乎，我们对于余数d相同的容量分别建一个单调队列，然后枚举x f[x*v+d]，进行转移即可。
#include<cstdio>
#include<cstring> inline int in(){
int x=,flag=;char ch=getchar();
while(ch!='-' && (ch>'' || ch<'')) ch=getchar();
if(ch=='-') flag=-,ch=getchar();
while(ch>='' && ch<='') x=x*+ch-'',ch=getchar();
return x*flag;
} int a[],b[],f[];
int w,v,k,n,V,l,r; void insert(int x,int y){
while(l<=r && b[r]<=y) r--;
a[++r]=x; b[r]=y;
} inline int Max(int a,int b){
if(a>b) return a;return b;
} int main(){
n=in(),V=in();
int Lim;
for(int i=;i<=n;i++){
v=in();w=in();k=in();
if(k==){
for(int j=V;j>=v;j--)
f[j]=Max(f[j],f[j-v]+w);
continue;
}
else if(k<){
for(int j=v;j<=V;j++)
f[j]=Max(f[j],f[j-v]+w);
continue;
}
if(V/v<k) k=V/v;
for(int d=;d<v;d++){
l=,r=;Lim=(V-d)/v;
for(int x=;x<=Lim;x++){
insert(x,f[x*v+d]-x*w);
if(a[l]<x-k) l++;
f[x*v+d]=b[l]+x*w;
}
}
}
printf("%d",f[V]);
return ;
}
codevs 3269 混合背包