给定 \(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\)为妙.
来源: https://www.cnblogs.com/ycx-akioi/p/Multiple-knapsack.html