Note: 本文最初于 2011年04月03日 星期日 20:33 在 hi.baidu.com/lydrainbowcat 发表。
若有n种物品，背包容量为m，物品体积、价值、最大使用次数为v,w,c，则朴素的动规方程为：f[i]=max{f[i-v*k]+w*k} (1<=k<=c)。
把所有可能达到的体积按照除以当前物品体积v的余数划分为0~v-1，则当余数为k(k∈[0,v-1])时又可划分为k,k+v,k+2*v…k+j*v…k+(m-k)/v*v
对于余数为k时的转移只会发生在以上列举出的几个体积上，可以建立关于以上几个体积的单调队列，以便于快速地找到最优决策。
这几个决策的体积和价值都不相同，直接没有可比性，所以利用体积为k+j*v这一特点，把需要插入队中的f[k+j*v]的价值减去j*w，就是当体积为k时的一个可以用于比较的“参考”价值。由于转移时，使用当前物品贡献的那一部分是二者之差，所以这与减掉j*w之前是等效的。
这样，每次求f[k+j*v]时，只需要在队列中找到一个最优的决策f[k+j’*v]，使得j-j’<=c即可，剩下的工作就只有维护单调队列了。
procedure insert(x,y:longint);//插入到一个价值单调递减，使用次数单调递增的队列中
begin
while (l<=r)and(b[r]<=y) do dec(r);
inc(r);a[r]:=x;b[r]:=y;
end;
begin
readln(n,m); //n为物品个数、m为背包容量
for i:=1 to n do
begin
read(v,w,c); //读入当前物品：v为物品体积、w为物品价值、c为物品可用次数
if m div v<c then c:=m div v; //最多可使用次数
for k:=0 to v-1 do //把所有的体积按除以v的余数划分为0~v-1
begin
l:=1;r:=0; //清空队列
for j:=0 to (m-k) div v do //余数为k的又分为k,v+k,2*v+k…j*v+k…
begin
insert(j,f[j*v+k]-j*w); //等效于把体积统一到k，价值减去j*w，这样比较优劣才有意义
while a[l]<j-c do inc(l); //删除次数超过c的
f[j*v+k]:=b[l]+j*w; //用队列头的值更新f[j*v+k]
end;
end;
end;
writeln(f[m]);
end.