单调队列优化多重背包问题
题目描述
有 n(0<n≤1000)种物品和一个容量为 V(0<V≤20000)的背包
第 i种物品最多有 si(0<si≤20000)件，每件体积是 vi(0<vi≤20000)，价值是 wi(0<wi≤20000)
求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大
多重背包—单调队列优化
对于 多重背包 分析，以及 二进制优化 这里不做额外讲解，直接分析 单调队列 优化方式
多重背包的原始状态转移方程
f(i,j)=max(f(i−1,j),f(i−1,j−v)+w,⋯,f(i−1,j−sv)+sw) 考虑用完全背包的优化方式来优化这个方程
f(i,j−v)=max(f(i−1,j−v),f(i−1,j−2v)+w,⋯,f(i−1,j−(s+1)v)+(s)w) 写出这个公式好像并不是那么管用
因为 完全背包 是一口气把所有体积全部用掉，即 max(a,b,c,d)=max(a,max(b,c,d))
然而 多重背包 对于每个物品的个数是有限制的，导致我们最终的等式是如下样子： max(a,b,c,d)≠max(a,max(b,c,d,e))
但是，我们可以把这个式子 继续 推导下去，直到背包体积被用到不能再用为止
其中 r=j mod vi，也可以理解为 完全背包 下把当前物品 选到不能再选 后，剩下的 余数
得到 f(i,r)=f(i−1,r)后，我们再利用 完全背包优化思路 往回倒推一遍
会惊奇的发现一个 滑动窗口求最大值 的模型，具体如下：
为了方便观察，把 f(i−1,j)改写成 fj
可能看上去还是有点复杂，为了更方便观察，去掉 w，然后把数组展开成一条链
具体如下图：
于是通过该 滑动窗口 ，我们就能在 线性 的时间里求出 i 阶段里，所有满足 j≡r mod (v)的 f(i,j)
滑动窗口 求 最大值 的实现，只需利用 队列 在队头维护一个 最大值 的 单调递减 的 单调队列 即可
为了更新所有 i 阶段里的状态 f(i,j)，我们只需再额外枚举所有的 余数 r 即可
不要忘记，滑动窗口内部比较最大值的时候，有一个在之前为了方便观察，被删掉的偏移量 w
要记得加上再比较
具体就是 当前下标 和该 最大值的下标 之间差了 x个 v，那么就要加上 x个 w 在上面公式里，还是比较容易看出的吧，就不做额外的推导了
代码
二维朴素版
时间复杂度：O(n×v)
空间复杂度：O(n×v)
滑动窗口的长度为 si+1
#include <iostream>
using namespace std;
const int N = 1010, M = 20010;
int n, m;
int v[N], w[N], s[N];
int f[N][M];
int q[M];
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; ++ i)
cin >> v[i] >> w[i] >> s[i];
for (int i = 1; i <= n; ++ i)
{
for (int r = 0; r < v[i]; ++ r)
{
int hh = 0, tt = -1;
for (int j = r; j <= m; j += v[i])
{
while (hh <= tt && j - q[hh] > s[i] * v[i])
hh ++ ;
while (hh <= tt && f[i - 1][q[tt]] + (j - q[tt]) / v[i] * w[i] <= f[i - 1][j])
-- tt;
q[ ++ tt] = j;
f[i][j] = f[i - 1][q[hh]] + (j - q[hh]) / v[i] * w[i];
}
}
}
cout << f[n][m] << endl;
return 0;
}
一维优化
时间复杂度：O(n×v)
空间复杂度：O(v)
和 01背包 的优化类似，观察到 状态转移方程，对于 i 阶段，只会用到 i-1 层的状态
因此可以采用 拷贝数组 或 滚动数组 的写法
拷贝数组写法
#include <iostream>
#include <cstring>
using namespace std;
const int N = 1010, M = 20010;
int n, m;
int v[N], w[N], s[N];
int f[M], g[M];
int q[M];
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; ++ i)
cin >> v[i] >> w[i] >> s[i];
for (int i = 1; i <= n; ++ i)
{
memcpy(g, f, sizeof g);
for (int r = 0; r < v[i]; ++ r)
{
int hh = 0, tt = -1;
for (int j = r; j <= m; j += v[i])
{
while (hh <= tt && j - q[hh] > s[i] * v[i])
hh ++ ;
while (hh <= tt && g[q[tt]] + (j - q[tt]) / v[i] * w[i] <= g[j])
-- tt;
q[ ++ tt] = j;
f[j] = g[q[hh]] + (j - q[hh]) / v[i] * w[i];
}
}
}
cout << f[m] << endl;
return 0;
}
滚动数组写法
#include <iostream>
using namespace std;
const int N = 1010, M = 20010;
int n, m;
int v[N], w[N], s[N];
int f[2][M];
int q[M];
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; ++ i)
cin >> v[i] >> w[i] >> s[i];
for (int i = 1; i <= n; ++ i)
{
for (int r = 0; r < v[i]; ++ r)
{
int hh = 0, tt = -1;
for (int j = r; j <= m; j += v[i])
{
while (hh <= tt && j - q[hh] > s[i] * v[i])
hh ++ ;
while (hh <= tt && f[(i - 1) & 1][q[tt]] + (j - q[tt]) / v[i] * w[i] <= f[(i - 1) & 1][j])
-- tt;
q[ ++ tt] = j;
f[i & 1][j] = f[(i - 1) & 1][q[hh]] + (j - q[hh]) / v[i] * w[i];
}
}
}
cout << f[n & 1][m] << endl;
return 0;
}
作者：一只野生彩色铅笔 链接：https://www.acwing.com/solution/content/53507/
这个视频讲的不是很清楚 和那个快慢指针似的 胡过去
提高课有视频 等买了回过头来想这个问题
💬 评论