浅谈多重背包的一些解法

一.朴素的多重背包

简介：多重背包是01背包的一种拓展形式。

朴素递推式: $dp(i,j)={\max }_{k=0}^{min(c_i,\lfloor \frac{j}{v_i}\rfloor )}dp(i-1,j-k\ast v_i)+k\ast w[i]$

注意空间优化后需要逆序更新背包.

复杂度:$O(n^3)$

二.二进制优化多重背包

核心思想:任意一个数X可以拆分成$logx$个2次幂相加。使得它们的线性组合能够恰好组成 $[1,x]$所有数.

例如:20 = 1 + 2 + 4 + 8 + (5) 即：[0,15]能够被组成，加上5后将范围平移到[0,20].

所以我们可以将其二进制拆分后，跑01背包即可.

代码：略.

复杂度:$O(n^{2}logn)$

三.单调队列优化多重背包

核心思想：    观察到问题一的朴素转移式,可以将背包体积V拆分成【物品的体积】个同余类。每一个同余类的转移是独立的。    然后转移本质是同余类中最近一段的dp值取最大值.且受限于物品的个数。所以就是一个长度固定的滑动窗口，可以用单调队列优化.

复杂度:O(NV)

#include<bits/stdc++.h> using namespace std; const int maxn = 1e3 + 5; int g[20005] , f[20005]; int Q[20005]; int v[maxn] , w[maxn] , s[maxn] ; int head , tail; int main() { int n , V ; cin >> n >> V; for (int i = 1 ; i <= n ; i++){ cin >> w[i] >> v[i] >> s[i] ; } for (int i = 1 ; i <= n ; i++){ memcpy(g , f , sizeof f); //枚举余数 for (int j = 0 ; j < w[i] ; j++){ //初始化队列 head = 1 , tail = 0; //同余类从小到大开始维护优先队列 for (int k = j ; k <= V ; k += w[i]){ //先将当前阶段的dp[k] 尝试放入优先队列 //考虑本层转移的时候， while(head <= tail && g[Q[tail]] + (k - Q[tail])/w[i] * v[i] <= g[k] ) tail--; //将k放入队尾 Q[++tail] = k; //维护s[i]长度的窗口 不能直接用tail - head + 1 去维护，如果出现一个 //特别大的数，那么队列长度会一直保持在1 if(head <= tail && (k - Q[head]) / w[i] > s[i]) head++; //维护的是单调递减队列，所以队首的值是最大值 f[k] = g[Q[head]] + (k - Q[head]) / w[i] * v[i]; } } } cout << f[V] << endl; return 0; }

四.多重背包计数

   问题描述：给定$N$种物品,第$i$种物品重量为$v_i$ ,数量为$c_i$.问你大小为$k\in [1,M]$的背包的组成方案数 ,要求时间复杂度为$O(NM)$,空间复杂度为$O(M)$ 朴素递推式: $dp(i,j)={\sum }_{k=0}^{min(c_i,\lfloor \frac{j}{v_i}\rfloor )}dp(i-1,j-k\ast v_i)$

前缀和优化

我们可以先把它当作完全背包处理。即得到前缀和。然后再差分减去一段前缀。 代码:

dp[0] = 1; for (int i = 1 ; i <= n ; i++){ for (int j = v[i] ; j <= m ; j++) dp[j] += dp[j - v[i]]; for (int j = m ; j >= (c[i] + 1) * v[i] ; j--) dp[j] -= dp[j - (c[i] + 1) * v[i]]; }

五.可撤销多重背包:

给定$N$种物品,第$i$种物品重量为$v_i$ ,数量为$c_i$ 记$f(i,j)$为不使用第$i$种物品时总重量为$j$的方案数,两种方案不同当且仅当至少有一种物品在两种方案里出现数量不同. 对每个$i=1,2,\cdots ,N和j=1,2,\cdots ,M.求f(i,j)$,要求时间复杂度为$O(NM)$,空间复杂度为$O(M)$

回到问题四:

观察上述式子不难发现:当我们计算完N时，我们可以对第N层操作进行撤销操作就可以得到前N - 1 个物品的状态。然后无论我们物品计算的顺序是怎样的，计算完N个之后dp数组都应该是一样的。所以我们可以对任意一个物品x进行撤回操作得到不含x的dp方案数. 代码:

// dp数组为求完前置问题的dp int x; while (cin >> x){ memset (tmp , 0 , sizeof tmp); for (int i = 0 ; i <= m ; i++) tmp[i] = dp[i]; for (int i = (c[x] + 1) * v[x] ; i <= m ; i++) tmp[i] += tmp[i - (c[x] + 1) * v[x]]; for (int i = m ; i >= v[i] ; i--) tmp[i] -= tmp[i - v[i]]; }

五的拓展：

01背包 和 完全背包 都能够撤销。原理同上.

六.多重背包的容斥解法

具体看我的下一篇文章: <容斥 + 背包 两则>