欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

多重背包问题

程序员文章站 2023-01-25 12:31:49
多重背包问题 给定$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\)为妙。