多重背包問題
- 2019 年 11 月 4 日
- 筆記
多重背包問題
給定(n)種物品，第(i)種共有(c_i)個，價值為(v_i)，重量為(w_i)。現在有一個背包，最大載重量為(m)。求若選一些物品放到背包里，最多能放的總價值是多少。
解法(bm1)
考慮將多重背包轉化為01背包。最簡單的想法是將(1)種物品直接拆分成(c_i)個相同的物品，然後01背包。這樣時間複雜度是(mathrm Oleft(sumlimits_{i=1}^nc_icdot mright))，太大了。考慮有沒有更優的拆分方式。
我們先看這樣一個問題：給定一個數(x)，問最少能選多少個數，使得(left[0,2^xright))內每個數都能被表示成一些選出的數之和。很顯然可以選(2^0,2^1,cdots,2^{x-1})這(x)個數，利用的是任何數都可以被二進位拆分這個原理。那麼如果給定一個數(x)，問的是最少能選多少個數，使得([0,x])內每個數都能被表示成一些選出的數之和呢？考慮找出(x)以內（包括(x)）最大的一個能被表示成(2)的整次冪(-1)的數(2^y-1)，那麼可以選(y)個數使得(left[0,2^yright))內每個數都能被表示成一些選出的數之和（顯然(y=lfloorlog_2(x+1)rfloor)）。那麼對於(left[2^y,xright])內的數呢？只需要再添一個數(x-2^y+1)即可。因為(forall iinleft[2^y,xright])，顯然(i-left(x-2^y+1right)inleft[2^{y+1}-x-1,2^y-1right]subseteqleft[0,2^yright))，那麼我們可以先湊出(i-left(x-2^y+1right))，再加一個(x-2^y+1)上去。
現在回到多重背包問題。第(i)種物品顯然可以被這樣拆分：((2^0v_i,2^0w_i),(2^1v_i,2^1w_i),cdots,left(2^{lfloorlog_2(c_i+1)rfloor-1}v_i,2^{lfloorlog_2(c_i+1)rfloor-1}w_iright),left(left(c_i-2^{lfloorlog_2(c_i+1)rfloor}+1right)v_i,left(c_i-2^{lfloorlog_2(c_i+1)rfloor}+1right)w_iright))（其中((x,y))表示一個價值為(x)，重量為(i)的物品）。這樣當且僅當(jin[0,c_i])時，(j)個第(i)種物品能被等價地表示出來，並且拆分成的物品的數量是(log)級別的。於是這樣拆分完再01背包，複雜度就有保證了：(mathrm Oleft(sumlimits_{i=1}^nlog_2c_icdot mright))。空間複雜度為拆分出來的物品個數+01背包所需空間：(mathrm Oleft(sumlimits_{i=1}^nlog_2c_i+mright))。
下面貼程式碼：
int nwn/*新物品個數*/,nwv[N*LOG_C_I+1]/*新物品價值*/,nww[N*LOG_C_I+1]/*新物品重量*/; int dp[M+1]; nwn=0; for(int i=1;i<=n;i++){//拆分每種物品 int _log=log2(c[i]+1); for(int j=0;j<_log;j++)nwv[++nwn]=v[i]<<j,nww[nwn]=w[i]<<j;//湊[0,2^_log) if(c[i]>(1<<_log)-1)nwv[++nwn]=v[i]*(c[i]-(1<<_log)+1),nww[nwn]=w[i]*(c[i]-(1<<_log)+1);//湊[2^_log,c[i]] } memset(dp,0,sizeof(dp)); for(int i=1;i<=nwn;i++)for(int j=m;j>=nww[i];j--)//01背包 dp[j]=max(dp[j],dp[j-nww[i]]+nwv[i]); //目標為dp[m]解法(bm2)
直接DP。設(dp_{i,j})表示當前考慮到第(i)個物品，背包容量還剩(j)時能放的最大價值。考慮枚舉第(i)個物品選了多少個，很容易得到轉移方程(dp_{i,j}=maxlimits_{k=0}^{minleft(c_i,leftlfloorfrac j{w_i}rightrfloorright)}left{dp_{i-1,j-kw_i}+kv_iright})。這個方程不管是列法上還是長相上都一臉單調隊列的樣子。於是我們將它變變形，分離狀態變數(j)和決策變數(k)（其實就是改為枚舉剩餘容量），得(dp_{i,j}=maxlimits_{kin[max(0,j-c_iw_i),j],kequiv jpmod{w_i}}left{dp_{i-1,k}-dfrac k{w_i}v_i+dfrac j{w_i}v_iright})。考慮到這裡面運算時會有小數，於是我們先加減後除，得(dp_{i,j}=maxlimits_{kin[max(0,j-c_iw_i),j],kequiv jpmod{w_i}}left{dfrac{w_idp_{i-1,k}-kv_i+jv_i}{w_i}right})。
這樣就很顯然怎麼單調隊列了吧。注意到(max)的條件里有一個同餘，於是我們可以把狀態變數分(j)為(w_i)組，每組中的成員分別(bmod w_i=0,1,cdots,w_i-1)，每組單獨跑一遍單調隊列，維護當前狀態的所有決策(k)中最大的(w_idp_{i-1,k}-kv_i)。而每到達一個(j)，將決策(k=j)入隊並維護隊尾嚴格單調遞減性，將(<max(0,j-c_iw_i))的決策出隊即可。
這樣時間複雜度等於狀態數，為(mathrm O(nm))，因為單調隊列是均攤(mathrm O(1))的。空間上呢，(dp)數組可以用滾動數組滾掉第一維，於是空間複雜度為(mathrm O(n+m))。
下面貼程式碼：
int q[M],head,tail;//單調隊列 int dp[2][M+1]; memset(dp,0,sizeof(dp)); for(int i=1;i<=n;i++)//考慮到第i個物品 for(int j=0;j<w[i];j++){//分組考慮 head=tail=0;//清空隊列 for(int k=j;k<=m;k+=w[i]){//遍歷此組中的所有狀態 while(head<tail&&q[head]<k-c[i]*w[i])head++;//出隊 while(head<tail&&w[i]*dp[i-1&1][q[tail-1]]-q[tail-1]*v[i]<=w[i]*dp[i-1&1][k]-k*v[i])tail--;//維護隊尾單調性 q[tail++]=k;//入隊 dp[i&1][k]=(w[i]*dp[i-1&1][q[head]]-q[head]*v[i]+k*v[i])/w[i];//此時隊首是最優決策 } } //目標為dp[n&1][m](bm2)兩種解法的比較
複雜度上，不管是時間還是空間，都是解法(2)更優。不過單調隊列相對難寫，要是在比賽中，不卡時間不卡常的話，還是寫解法(1)為妙。
