多重背包問題 給定$n$種物品，第$i$種共有$c_i$個，價值為$v_i$，重量為$w_i$。現在有一個背包，最大載重量為$m$。求若選一些物品放到背包里，最多能放的總價值是多少。 解法$\bm1$ 考慮將多重背包轉化為01背包。最簡單的想法是將$1$種物品直接拆分成$c_i$個相同的物品，然後0 ...
多重背包問題
給定\(n\)種物品，第\(i\)種共有\(c_i\)個，價值為\(v_i\)，重量為\(w_i\)。現在有一個背包，最大載重量為\(m\)。求若選一些物品放到背包里，最多能放的總價值是多少。
解法\(\bm1\)
考慮將多重背包轉化為01背包。最簡單的想法是將\(1\)種物品直接拆分成\(c_i\)個相同的物品，然後01背包。這樣時間複雜度是\(\mathrm O\left(\sum\limits_{i=1}^nc_i\cdot m\right)\)，太大了。考慮有沒有更優的拆分方式。
我們先看這樣一個問題：給定一個數\(x\)，問最少能選多少個數，使得\(\left[0,2^x\right)\)內每個數都能被表示成一些選出的數之和。很顯然可以選\(2^0,2^1,\cdots,2^{x-1}\)這\(x\)個數，利用的是任何數都可以被二進位拆分這個原理。那麼如果給定一個數\(x\)，問的是最少能選多少個數，使得\([0,x]\)內每個數都能被表示成一些選出的數之和呢？考慮找出\(x\)以內（包括\(x\)）最大的一個能被表示成\(2\)的整次冪\(-1\)的數\(2^y-1\)，那麼可以選\(y\)個數使得\(\left[0,2^y\right)\)內每個數都能被表示成一些選出的數之和（顯然\(y=\lfloor\log_2(x+1)\rfloor\)）。那麼對於\(\left[2^y,x\right]\)內的數呢？只需要再添一個數\(x-2^y+1\)即可。因為\(\forall i\in\left[2^y,x\right]\)，顯然\(i-\left(x-2^y+1\right)\in\left[2^{y+1}-x-1,2^y-1\right]\subseteq\left[0,2^y\right)\)，那麼我們可以先湊出\(i-\left(x-2^y+1\right)\)，再加一個\(x-2^y+1\)上去。
現在回到多重背包問題。第\(i\)種物品顯然可以被這樣拆分：\((2^0v_i,2^0w_i),(2^1v_i,2^1w_i),\cdots,\left(2^{\lfloor\log_2(c_i+1)\rfloor-1}v_i,2^{\lfloor\log_2(c_i+1)\rfloor-1}w_i\right),\left(\left(c_i-2^{\lfloor\log_2(c_i+1)\rfloor}+1\right)v_i,\left(c_i-2^{\lfloor\log_2(c_i+1)\rfloor}+1\right)w_i\right)\)（其中\((x,y)\)表示一個價值為\(x\)，重量為\(y\)的物品）。這樣當且僅當\(j\in[0,c_i]\)時，\(j\)個第\(i\)種物品能被等價地表示出來，並且拆分成的物品的數量是\(\log\)級別的。於是這樣拆分完再01背包，複雜度就有保證了：\(\mathrm O\left(\sum\limits_{i=1}^n\log_2c_i\cdot m\right)\)。空間複雜度為拆分出來的物品個數+01背包所需空間：\(\mathrm O\left(\sum\limits_{i=1}^n\log_2c_i+m\right)\)。
下麵貼代碼：
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}=\max\limits_{k=0}^{\min\left(c_i,\left\lfloor\frac j{w_i}\right\rfloor\right)}\left\{dp_{i-1,j-kw_i}+kv_i\right\}\)。這個方程不管是列法上還是長相上都一臉單調隊列的樣子。於是我們將它變變形，分離狀態變數\(j\)和決策變數\(k\)（其實就是改為枚舉剩餘容量），得\(dp_{i,j}=\max\limits_{k\in[\max(0,j-c_iw_i),j],k\equiv j\pmod{w_i}}\left\{dp_{i-1,k}-\dfrac k{w_i}v_i+\dfrac j{w_i}v_i\right\}\)。考慮到這裡面運算時會有小數，於是我們先加減後除，得\(dp_{i,j}=\max\limits_{k\in[\max(0,j-c_iw_i),j],k\equiv j\pmod{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\)，每組單獨跑一遍單調隊列，維護當前狀態的所有決策中使\(w_idp_{i-1,k}-kv_i\)最大的決策\(k\)。而每到達一個\(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\)為妙。
