c/c++语言开发共享多重背包问题

多重背包问题

给定(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)，重量为(y)的物品）。这样当且仅当(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)，每组单独跑一遍单调队列，维护当前状态的所有决策中使(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)为妙。