详细请查看注释:也就干了一下午加一个晚上!
尽可能将所有不好理解的地方解释了一遍!
参考代码:
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 20010;
int n, m, q[N], g[N], f[N];
/*
多重背包问题:(物品限制为s[i]个,我们考虑理想状态,一定可以选到s[i]个,边界情况单独处理即可!)
状态表示:f[i][j]表示从前i个物品中选,体积不超过j的集合!属性:最大值!
状态计算:
f[i][j] = max(f[i-1][j],f[i-1][j-v]+w,f[i-1][j-2v]+2w, ... 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-sv]+(s-1)w, f[i-1][j-(s+1)v]+sw)
会发现一个问题:与完全背包不同,最后会多出一项,我们上下无法对其进行替换操作!
因此:我们考虑一下
f[i][j-2v]
f[i][j-3v]
...
f[i][r](其中r = j % v)
惊奇的发现:他们的项数一样的都是s + 1项,第i个物品的个数为[0, s]
我们画一个数轴:__|____|____|____|____|_____|________________|_____|_____|_____|_
r r+v r+2v r+3v ...... j-kv j-2v j-v j
数轴每一项都表示:f[i-1][r],f[i-1][r+v]...f[i-1][j-v],f[i-1][j]
我们计算f[i][j-kv](k=0,1,2...s)时候:对应到数轴上就是计算他自己之前(包括自己)和之前s个位置的最大值!
(注意:这里先忽略状态计算中的偏移量w)
举例:计算f[i][j-v],s = 3,就是计算他自己和之前三项的最大值,即:f[i-1][j-v],f[i-1][j-2v],f[i-1][j-3v],f[i-1][j-4v]
小小的发现:
1. 计算某一项f[i][j]会发现他的值仅与他和他前面s项决定,也就是长度固定的滑动窗口!
2. 在滑动窗口里面求最大值,自然而然的想到单调队列!因此我们可以使用单调队列来优化这一过程!
1. 维护单调队列长度为s,超过s直接删掉
2. 维护单调队列的单调性,用不到的数据直接删掉
3. 单调队列单调依据:按价值单调递减!
另外得到一个规律:
1. 完全背包其实就是求所有前缀的最大值(个数无限制,可以一直-v直到r)
2. 多重背包其实就是求长度固定的滑动窗口内的最大值(个数有限制,最多只能-sv)
还有一个问题:我们之前忽略的偏移量的处理!
根据上面的状态计算的公式找两个规律:
1. 对于某一个状态f[i][j]从左到右看w是逐渐+1增长
2. 队友多个状态f[i][j]从对其放下从上向下看w是逐渐-1下降
嗯:有点复杂!
f[i][j] = max(f[i-1][j],f[i-1][j-v]+w,f[i-1][j-2v]+2w, ... f[i-1][j-sv]+sw)
从状态计算式子来看,后面的一项比前面一项多w,做一个等价变形,先全部-sw,最后再+sw
f[i][j] = max(f[i-1][j]-sw,f[i-1][j-v]-(s-1)w, .....f[i-1][j-sv]) + sw
这个式子从右向左和数轴从左向右是对应的,也就对应数轴如下:
__|____|____|____|____|_____|________________|_____|_____|_____|_
r r+v r+2v r+3v ...... j-kv j-2v j-v j
-0w -1w -2w ... -sw
偏移量规律:r + kv ---> -kw
由于f[i][]的计算只用到f[i-1]因此我们使用滚动数组进行优化即可!
1. g数组保存f[i-1]
2. f数组保存f[i]
注意点:
1. 单调队列q保存的是第二维的体积!
2. 单调队列的单调性指的是体积对应的价值的单调性,保存的体积不一定单调!
大概就是这样了!更加详细查看代码内的注释!
*/
int main(){
cin >> n >> m;
for(int i = 0; i < n; i ++){
int v, w, s; cin >> v >> w >> s;
// 保存上一层f[i - 1]到g
memcpy(g, f, sizeof f);
// 枚举第二维的体积j
for(int j = 0; j < v; j ++){
int hh = 0, tt = -1;
// 枚举第i个物品选几个的体积(从余数j开始,即k初始值应该是j % v,由于j小于v,因此就是j了)
for(int k = j; k <= m; k += v){
// 1. 维护长度为s的滑动窗口!体积范围为:[k - s * v, k]
// q[hh]:滑动窗口的左端点,保存的是体积
// k - s * v:当前体积为k,长度为s的滑动窗口占用的体积为s * v
if(hh <= tt && q[hh] < k - s * v) hh ++;
// 2. 当前状态f[k]计算!
/*
该状态由维护的单调队列的队首最大值g[q[hh]]决定!
由上方分析的偏移量规律,可以得到本处的偏移量应该为:(k - q[hh]) / v * w
*/
if(hh <= tt) f[k] = max(f[k], g[q[hh]] + (k - q[hh]) / v * w);
// 3. 维护单调队列,保证滑动窗口内的体积对应的价值单调递减!(若队尾体积对应的价值小于)
/*
一般比较为:g[q[tt]] <= g[k],但每一层都要有一个偏移量!如下:
g[q[tt]]:队尾体积对应的价值
(q[tt] - j) / v * w:减去一个偏移量,偏移量规律:r + kv ---> -kw,k = (q[tt] - j) / v
g[k]:上一层体积为k对应的价值
(k - j) / v * w:减去一个偏移量,偏移量规律:r + kv ---> -kw,k = (q[tt] - j) / v
注意:这里的j就是 j % v 的 j
*/
while(hh <= tt && g[q[tt]] - (q[tt] - j) / v * w <= g[k] - (k - j) / v * w) tt --;
q[++ tt] = k;
}
}
}
cout << f[m] << endl;
return 0;
}
写的很好,必须赞一个