Mato is No.1

多重背包問題樸素時間復(fù)雜度為O(NMS)（這里S是所有物品的數(shù)量s之和），經(jīng)過二進(jìn)制優(yōu)化后時間復(fù)雜度為O(NMlog2S)，這個復(fù)雜度已經(jīng)能夠應(yīng)付大多數(shù)題了，但對于某些特別卡時間的題（比如N*M=10⁷的)，仍然會TLE。這時，可以用單調(diào)隊(duì)列優(yōu)化，時間復(fù)雜度降為O(NM)。

首先看一下多重背包問題的樸素轉(zhuǎn)移方程：
F[i][j] = max{F[i-1][j-x*w[i]]+x*v[i]} (0<=x<=s[i], j>=x*w[i])
如果使用滾動數(shù)組，忽略i這一維，設(shè)w0=w[i]，v0=v[i]，s0=s[i]，得：
F[j] = max{F[j-x*w0]+x*v0} (0<=x<=s0, j>=x*w0)
看上去這和單調(diào)隊(duì)列木有神馬關(guān)系，因?yàn)闆Q策下標(biāo)（j-x*w0）不是一個整數(shù)區(qū)間，中間是有間隔的。然而可以發(fā)現(xiàn)，這個方程的限制條件“0<=x<=s0，j>=x*w0”，也就是x的下界是max{0, j/w0（下取整）}，當(dāng)j單調(diào)遞增時，這個下界也是單調(diào)遞增的。這滿足單調(diào)隊(duì)列優(yōu)化的條件中的“決策下標(biāo)的下界單調(diào)”……不是，還不能這樣說，因?yàn)檫@里的決策下標(biāo)是j-x*w0，而不是x。
那么怎樣才可以把決策下標(biāo)變?yōu)閤？

將決策下標(biāo)按照模w0的余數(shù)進(jìn)行分類，可以分成w0類，分別對應(yīng)模w0余0、余1……余(w0-1)的情況。這時，上面方程中的所有決策下標(biāo)j-x*w0都是同一類的。進(jìn)一步，設(shè)q =j/w0（下取整），r=j%w0，則j=q*w0+r，對于某個決策下標(biāo)j'，設(shè)k=(j'-r)/w0，即j'=k*w0+r。顯然可以發(fā)現(xiàn)，k的取值范圍是：k>=0且q-s0<=k<=q，也即k的下界是max{0, q-s0}——隨j的單調(diào)而單調(diào)。
然后，轉(zhuǎn)移方程可以改為（這里把r當(dāng)成一個已知量了）：
F[q*w0+r] = max{F[k*w0+r]+(q-k)*v0} (k>=0且q-s0<=k<=q)
即F[q*w0+r]=max{F[k*w0+r]-k*v0}+q*v0 (k>=0且q-s0<=k<=q)
設(shè)G[k]=F[k*w0+r]得：
G[q]=max{G[k]-k*v0}+q*v0 (k>=0且q-s0<=k<=q)
這個方程已經(jīng)可以使用單調(diào)隊(duì)列來優(yōu)化了！

這樣可以得出算法：
（1）從1到n，枚舉i，建立w[i]個空的單調(diào)隊(duì)列，每個隊(duì)列的元素都是兩個int值：(k, val)，表示轉(zhuǎn)換后下標(biāo)和決策值(G[k]-k*v[i])；
（2）從0到m，枚舉j，得出q、r的值，對于隊(duì)列r：
【1】刪去隊(duì)首過時（k<q-m[i]）的元素；
【2】F[j]入隊(duì)（這里的F[j]指上一階段的F[j]，即F[i-1][j]。因此這一步操作一定要先進(jìn)行），刪去隊(duì)尾所有決策值val不大于(F[j]-q*v[i])的元素。
【3】取出隊(duì)首結(jié)點(diǎn)，其val值加上q*v[i]后即為本階段F[j]的值。
最后F[m]即為結(jié)果。總時間復(fù)雜度為O(NM)。

其實(shí)這個是可以推廣的，即對于如下形式的轉(zhuǎn)移方程（其中H、G和W均為常量，B[i]為決策下標(biāo)的下界，隨i單調(diào)）：
F[i] = opt{F[i-x*H+W]}+G (B[i]<=i-x*H+W<i，x∈N）
都可以用上述的辦法進(jìn)行轉(zhuǎn)化，從而進(jìn)行單調(diào)隊(duì)列優(yōu)化。