多次背包
多次背包问题：给定 n 种物品和一个背包。第 i 种物品 的价值是 Wi ，其体积
为 Vi，数量是 Ki件，背包的容量为 C。可以任意选择装入背包中的物品，求装入背
包中物品的最大总价值。

方法一：可以把此物品拆分成Ki个只能用一次的物品，直接套用 0-1 背包问题的经典动规实现，但是效率太低了，需要寻找更高效的算法。此算法时间复杂度为O(C*∑(Ki))

方法二：拆分成体积和价值分别为原来1, 2 , 4..   2^m,    Ki-2^m 倍的几个物品，用0-1背包求解。 时间复杂度为O(C*∑([log2Ki]))

方法三（本文重点）：（对单调队列没有了解的请参见原论文[本文结尾链接]）对于第 i 种物品来说，已知体积 v，价值 w，数量 k，那么可以按照当前枚举的体积 j 对v的余数把整个动规数组分成 v份，以下是 v=3 的情况：
j             0 1 2 3 4 5 6 7 8 ……
j mod v   0 1 2 0 1 2 0 1 2 ……

我们可以把每一份分开处理，假设余数为 d。
编号j         0     1        2            3           4             5         ……
对应体积 d    d+v    d+2*v     d+3*v    d+4*v      d+5*v    ……

现在看到分组以后，编号 j 可以从 j-k 到 j-1 中的任意一个编号转移而来（因为相邻的体积正好相差 v） ，这看上去已经和区间最大值有点相似了。但是注意到由于体积不一样，显然体积大的价值也会大于等于体积小的，直接比较是没有意义的，所以还需要把价值修正到同一体积的基础上。比如都退化到 d，也就是说用 F[j*v+d]- j*w来代替原来的价值进入队列。

对于物品i，伪代码如下

1. FOR d: = 0 TO v-1                     //枚举余数，分开处理
2.   清空队列
3.   FOR j: = 0 TO (C-d) div v           //j 枚举标号，对应体积为 j*v+d
4.    INSERT j , F[ j*v+d ] – j * w      //插入队列
5.    IF A[ L ] < j - k THEN L + 1 → L //如果队列的首元素已经失效
6.    B[ L ] + j * w → F[ j*v+d ]       //取队列头更新
7.   END FOR
8. END FOR

已知单调队列的效率是 O(n)，那么加上单调队列优化以后的多次背包，
效率就是 O(n*C)了。
（详细请参见原论文）

==========================================================

完整程序如下(Pascal)：

var
   a,b,f:array[0..100000] of longint;
   m,s,c,n,t,i,j,l,r,d:longint;
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,t);              //读入数据 n为物品个数 t为背包容量
   for i:=1 to n do
   begin
      read(m,s,c);         //读入当前物品 m为物品体积、s为物品价值、c为物品可用次数（0表示无限制）
      if (c=0)or(t div m<c) then c:=t div m;
      for d:=0 to m-1 do
      begin
         l:=1;r:=0;     //清空队列
         for j:=0 to (t-d) div m do
         begin
            insert(j,f[j*m+d]-j*s);   //将新的点插入队列
            if a[l]<j-c then inc(l);   //删除失效点
            f[j*m+d]:=b[l]+j*s;        //用队列头的值更新f[j*m+d]
         end;
      end;
   end;
   writeln(f[t]);
end.

==========================================================

原文地址：http://wenku.baidu.com/view/8ab3daef5ef7ba0d4a733b25.html

其实这只是一种算法，另一种O(VN)算法见：http://hi.baidu.com/sy2006ppkdc/blog/item/f86374256d84a91a8b82a131.html（此方法使用类似线性动规的算法，常数稍大，内存较大）