多次背包
多次背包問(wèn)題：給定 n 種物品和一個(gè)背包。第 i 種物品 的價(jià)值是 Wi ，其體積
為 Vi，數(shù)量是 Ki件，背包的容量為 C。可以任意選擇裝入背包中的物品，求裝入背
包中物品的最大總價(jià)值。

方法一：可以把此物品拆分成Ki個(gè)只能用一次的物品，直接套用 0-1 背包問(wèn)題的經(jīng)典動(dòng)規(guī)實(shí)現(xiàn)，但是效率太低了，需要尋找更高效的算法。此算法時(shí)間復(fù)雜度為O(C*∑(Ki))

方法二：拆分成體積和價(jià)值分別為原來(lái)1, 2 , 4..   2^m,    Ki-2^m 倍的幾個(gè)物品，用0-1背包求解。 時(shí)間復(fù)雜度為O(C*∑([log2Ki]))

方法三（本文重點(diǎn)）：（對(duì)單調(diào)隊(duì)列沒(méi)有了解的請(qǐng)參見(jiàn)原論文[本文結(jié)尾鏈接]）對(duì)于第 i 種物品來(lái)說(shuō)，已知體積 v，價(jià)值 w，數(shù)量 k，那么可以按照當(dāng)前枚舉的體積 j 對(duì)v的余數(shù)把整個(gè)動(dòng)規(guī)數(shù)組分成 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 ……

我們可以把每一份分開(kāi)處理，假設(shè)余數(shù)為 d。
編號(hào)j         0     1        2            3           4             5         ……
對(duì)應(yīng)體積 d    d+v    d+2*v     d+3*v    d+4*v      d+5*v    ……

現(xiàn)在看到分組以后，編號(hào) j 可以從 j-k 到 j-1 中的任意一個(gè)編號(hào)轉(zhuǎn)移而來(lái)（因?yàn)橄噜彽捏w積正好相差 v） ，這看上去已經(jīng)和區(qū)間最大值有點(diǎn)相似了。但是注意到由于體積不一樣，顯然體積大的價(jià)值也會(huì)大于等于體積小的，直接比較是沒(méi)有意義的，所以還需要把價(jià)值修正到同一體積的基礎(chǔ)上。比如都退化到 d，也就是說(shuō)用 F[j*v+d]- j*w來(lái)代替原來(lái)的價(jià)值進(jìn)入隊(duì)列。

對(duì)于物品i，偽代碼如下

1. FOR d: = 0 TO v-1                     //枚舉余數(shù)，分開(kāi)處理
2.   清空隊(duì)列
3.   FOR j: = 0 TO (C-d) div v           //j 枚舉標(biāo)號(hào)，對(duì)應(yīng)體積為 j*v+d
4.    INSERT j , F[ j*v+d ] – j * w      //插入隊(duì)列
5.    IF A[ L ] < j - k THEN L + 1 → L //如果隊(duì)列的首元素已經(jīng)失效
6.    B[ L ] + j * w → F[ j*v+d ]       //取隊(duì)列頭更新
7.   END FOR
8. END FOR

已知單調(diào)隊(duì)列的效率是 O(n)，那么加上單調(diào)隊(duì)列優(yōu)化以后的多次背包，
效率就是 O(n*C)了。
（詳細(xì)請(qǐng)參見(jiàn)原論文）

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

完整程序如下(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);              //讀入數(shù)據(jù) n為物品個(gè)數(shù) t為背包容量
   for i:=1 to n do
   begin
      read(m,s,c);         //讀入當(dāng)前物品 m為物品體積、s為物品價(jià)值、c為物品可用次數(shù)（0表示無(wú)限制）
      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;     //清空隊(duì)列
         for j:=0 to (t-d) div m do
         begin
            insert(j,f[j*m+d]-j*s);   //將新的點(diǎn)插入隊(duì)列
            if a[l]<j-c then inc(l);   //刪除失效點(diǎn)
            f[j*m+d]:=b[l]+j*s;        //用隊(duì)列頭的值更新f[j*m+d]
         end;
      end;
   end;
   writeln(f[t]);
end.

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

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

其實(shí)這只是一種算法，另一種O(VN)算法見(jiàn)：http://hi.baidu.com/sy2006ppkdc/blog/item/f86374256d84a91a8b82a131.html（此方法使用類(lèi)似線性動(dòng)規(guī)的算法，常數(shù)稍大，內(nèi)存較大）