Posted on 2011-07-05 18:00
Mato_No1 閱讀(5999)
評論(3) 編輯 收藏 引用 所屬分類:
動態規劃
多重背包問題樸素時間復雜度為O(NMS)（這里S是所有物品的數量s之和），經過二進制優化后時間復雜度為O(NMlog2S)，這個復雜度已經能夠應付大多數題了，但對于某些特別卡時間的題（比如N*M=107的)，仍然會TLE。這時，可以用單調隊列優化，時間復雜度降為O(NM)。
首先看一下多重背包問題的樸素轉移方程：
F[i][j] = max{F[i-1][j-x*w[i]]+x*v[i]} (0<=x<=s[i], j>=x*w[i])
如果使用滾動數組，忽略i這一維，設w0=w[i]，v0=v[i]，s0=s[i]，得：
F[j] = max{F[j-x*w0]+x*v0} (0<=x<=s0, j>=x*w0)
看上去這和單調隊列木有神馬關系，因為決策下標（j-x*w0）不是一個整數區間，中間是有間隔的。然而可以發現，這個方程的限制條件“0<=x<=s0，j>=x*w0”，也就是x的下界是max{0, j/w0（下取整）}，當j單調遞增時，這個下界也是單調遞增的。這滿足單調隊列優化的條件中的“決策下標的下界單調”……不是，還不能這樣說，因為這里的決策下標是j-x*w0，而不是x。
那么怎樣才可以把決策下標變為x？
將決策下標按照模w0的余數進行分類，可以分成w0類，分別對應模w0余0、余1……余(w0-1)的情況。這時，上面方程中的所有決策下標j-x*w0都是同一類的。進一步，設q =j/w0（下取整），r=j%w0，則j=q*w0+r，對于某個決策下標j'，設k=(j'-r)/w0，即j'=k*w0+r。顯然可以發現，k的取值范圍是：k>=0且q-s0<=k<=q，也即k的下界是max{0, q-s0}——隨j的單調而單調。
然后，轉移方程可以改為（這里把r當成一個已知量了）：
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)
設G[k]=F[k*w0+r]得：
G[q]=max{G[k]-k*v0}+q*v0 (k>=0且q-s0<=k<=q)
這個方程已經可以使用單調隊列來優化了！
這樣可以得出算法：
（1）從1到n，枚舉i，建立w[i]個空的單調隊列，每個隊列的元素都是兩個int值：(k, val)，表示轉換后下標和決策值(G[k]-k*v[i])；
（2）從0到m，枚舉j，得出q、r的值，對于隊列r：
【1】刪去隊首過時（k<q-m[i]）的元素；
【2】F[j]入隊（這里的F[j]指上一階段的F[j]，即F[i-1][j]。因此這一步操作一定要先進行），刪去隊尾所有決策值val不大于(F[j]-q*v[i])的元素。
【3】取出隊首結點，其val值加上q*v[i]后即為本階段F[j]的值。
最后F[m]即為結果。總時間復雜度為O(NM)。
其實這個是可以推廣的，即對于如下形式的轉移方程（其中H、G和W均為常量，B[i]為決策下標的下界，隨i單調）：
F[i] = opt{F[i-x*H+W]}+G (B[i]<=i-x*H+W<i，x∈N）
都可以用上述的辦法進行轉化，從而進行單調隊列優化。