多重背包问题

多重背包问题

给定\(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\)为妙。