多次背包
多次背包問題：給定 n 種物品和一個背包。第 i 種物品 的價值是 Wi ，其體積
為 Vi，數量是 Ki件，背包的容量為 C?？梢匀我膺x擇裝入背包中的物品，求裝入背
包中物品的最大總價值。

方法一：可以把此物品拆分成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（此方法使用類似線性動規的算法，常數稍大，內存較大）