单调队列优化多重背包问题
直接上截图:
通过对状态转移方程的分析可以推出:能用滑动窗口求最值的方法优化算法
状态转移方程:f[j] = max( f[k] + (j - k) / v * w) 其中j - s*v <= k <= j --> 长度 = (j-(j-s*v))/v + 1 = s+1
本层 上层 --> 更新时要用g[N]保存上层的f[N] (在不考虑s个物品体积超出j的前提下)
简写如下:
f[j] = max(j ~ j - s*v)
f[j-v] = max(j - v ~ j - (s+1) * v)
......
f[j%v] = max(f[j%v] + (j - j%v) / v * w) //考虑有上限,最后一项只有一个,往上依次递增直到长度达到s+1
令r = j%v,则可得出上图中的数轴,由分析可得可用滑动窗口问题来优化
对滑动窗口及偏移量的分析:
1、数轴上对应的数字本身为上一层的f[](即代码中的g[]),但在求最大值的实际比较中要加入偏移量:
如:此时要求的是本层f[k], 队尾元素为g[i], 则比较时应该用:g[i] + (k - i) / v * w
f[k] = max( g[i] + (k - i) / v * w)
2、我们要求的是f[k], 则移入窗口的是上层的g[k], 在比较是应该加上偏移量:g[k] + (k - k) / v * w = g[k]
综合1、2可得代码第27行:while(hh <= tt && g[q[tt]] + (k - q[tt]) / v * w <= g[k]) t--;
3、用滑动窗口的最大值来更新本层f[k] = g[q[hh]] + (k - g[q[hh]]) / v * w
关于枚举所有余数的问题分析(n为物品个数,V为最大容量):
1、目的:求第n层的f[V]
2、要求第n层的f[V], 就要求第n-1层的f[k],k满足 V - s*v <= k <= V, 其中v为第n层的v
3、要求第n-1层的f[k], 就要求第n-2层的f[k],k满足 V - s*v <= k <= V, 其中v为第n-1层的v
......
由于每一层的v都不同且不确定,所以每个k的值都不确定,所以要通过枚举所有余数,以求出所有的f[0] ~ f[V];
参考文献
y总算法提高课
C++ 代码
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 20010;
int n, V;
int f[N], g[N], q[N];
int main()
{
cin >> n >> V;
for(int i = 0; i < n; i++)
{
int v, w, s;
cin >> v >> w >> s;
memcpy(g, f, sizeof f);
for(int j = 0; j < v; j++)
{
int hh = 0, tt = -1;
for(int k = j; k <= V; k += v)
{
if(hh <= tt && q[hh] < k - s*v) hh++;
while(hh <= tt && g[q[tt]] + (k - q[tt]) / v * w <= g[k]) tt--;
q[++tt] = k;
f[k] = g[q[hh]] + (k - q[hh]) / v * w;
}
}
}
cout << f[V] << endl;
return 0;
}
以上为我对滑动窗口优化多重背包问题代码的理解,若有问题请各位大佬指正
大佬写的太棒了