多重背包问题
给定(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)为妙。
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/601074.html