这里是简介
1.1 前言
多重背包，想必看到这篇博文的人应该都知道了，这里仅仅列出伪代码（$n$为物品个数，$m$为背包容积）
for i := 1 to N
for j := 0 to M
for k := 0 to c[i]
f[i][j] = max(f[i - 1][j - k * v[i]] + k * w[i])
显然，这种算法的复杂度是很不可取的，于是我们来考虑优化
1.2 优化方式
设$c,v,w$分别为当前物品的个数，体积，价值，根据原始转移方程可知，$fi$一定是由$f{i-1}$转移而来，所以$c,v,w$不用开数组（有的$OJ$竟然会卡空间…），为了方便说明，以下设数组$g$表示数组$f_{i-1}$，于是方程简化为：
f[j] = max(g[j - k * v] + k * w) //0≤k≤c
显然，就算不简化，我们也能看出：$fj$只从$f{j-vi},f{j-vi\times 2}…f{j-v_i\times c}$转移过来，且对于每一个这其中的$j$，都有如下性质：它们模上$v$后的余数相同，于是我们将其模$v$后的余数拎出来考虑，循环可以这样写：
for i := 1 to N
for j := 0 to v - 1
...
接下来呢，就要枚举系数$k$了
for (k = 0; k * v + j <= M; ++k)
你不觉得枚举系数很麻烦吗？这样就好了
for (k = j; k <= M; k += v)
接下来来看转移方程，根据之前得出的转移方程，显然我们是要找到在一个长度为$c$的区间内最大的$g[j - k \times v] + k\times w$，可以用单调队列来存储，于是又有
while (l <= r && (k - q[l]) / v >= c) ++l;
while (l <= r && f[i - 1][k] - f[i - 1][q[r]] >= (k - q[r]) / v * w) --r;
q[++r] = k;
f[i][k] = f[i - 1][q[l]] + (k - q[l]) / v * w;
- 这里的$(k-q_i)/v$代表两个数的系数相差多少，$+1$后则代表所跨区间的长度,这里的$(k - q[l]) / v \geq c$用于防止区间长度大于$c$，相当于$(k - q[l]) / v + 1 > c$，不满足条件则弹出队首元素。
- 当在队列中插入新元素时，需有$g[k]+k/v\times w \geq g[q[r]]+q[r]/v\times w$，这是根据单调队列所存储元素的定义得出的，移项后得$g[k]-g[q[r]]>=(k-q[r])/v\times w$，巧妙地避免了余数的问题。
- 我们只插入$k$就好了，不然不方便$\Delta w$的计算。
- 这里取队首再加上$\Delta w=(k-q[l])/v\times w$就好了
1.3 代码
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int N = 1e3 + 10, M = 1e4 + 10;
int n, m, f[N][M], v, w, c, q[M], l, r, ans;
int main () {
scanf ("%d%d", &n, &m);
for (int i = 1; i <= n; ++i) {
scanf ("%d%d%d", &c, &v, &w);
c = min (c, m / v);
for (int j = 0; j < v; ++j) {
l = 1; r = 0;
for (int k = j; k <= m; k += v) {
while (l <= r && (k - q[l]) / v >= c) ++l;
while (l <= r && f[i - 1][k] - f[i - 1][q[r]] >= (k - q[r]) / v * w) --r;
q[++r] = k;
f[i][k] = f[i - 1][q[l]] + (k - q[l]) / v * w;
}
}
}
for (int i = 1; i <= m; ++i)
ans = max (ans, f[n][i]);
printf ("%d\n", ans);
return 0;
}
1.4 注意
- 单调队列初始化为$l=1,r=0$，且在循环$j$内初始化
- 单调队列长度开到$M$，因为有可能出现$v=1$的情况
- 最后答案不一定存在$f_{n,m}$里面，要在$1…m$扫一遍
- 一定要记得$c=min(c,m/v)$，为了防止背包溢出