多重背包 III
该问题如果使用多重背包II的解法,那么是会超时的,因为如果进行压缩的话,他的时间复杂度大概为$O(N \times V \times \log{V})$,大概的一个数值应该为$1000 \times 20000 \times 15 > 10^8$,所以对于$1S$的时间限制是不可以过的
分析
对于状态转移的方程:$f[i][j] = max(f[i-1][j], f[i-1][j - k * v] + k * w),j\in [v,m],k\in [0,S]$
对该方程进行细分:
$f[i][j] = max(f[i-1][j],f[i-1][j - v] + w,f[i-1][j-2\times v] + 2 \times w,f[i-1][j-3\times v] + 3 \times w) ,\ldots ,f[i-1][j-s\times v] +s \times w)$
$f[i][j+v] = max(f[i-1][j + v],f[i-1][j ] + w,f[i-1][j- v] + 2 \times w,f[i-1][j-2\times v] + 3 \times w) ,\ldots ,f[i-1][j-(s-1)\times v] +s \times w)$
$f[i][j+2\times v] = max(f[i-1][j + 2 \times v],f[i-1][j + v] + w,f[i-1][j] + 2 \times w,f[i-1][j-1\times v] + 3\times w) ,\ldots ,f[i-1][j-(s-2)\times v] +s \times w)$
将相应的位置对其后,可以发现他们之间有很多相似的地方,最后又都是求这些区间的一个最大值,所以才需要使用单调队列进行优化
在此之前,对于该问题来说,他的二维也是可以优化为一维的,只需要在更新之前,对前一次的状态进行一次拷贝即可(memcpy)
memcpy(pre,f,sizeof f); // pre数组即为前一次的状态
使用单调队列的优化
对于每一个状态$f[0\rightarrow m]$,他都有这如下的关系:
$f[0] = max(pre[0],pre[0+v] + w,pre[0+2\times v] + 2\times w,pre[0 + 3 \times v + 3\times w],\ldots,pre[0 + s \times v]+s\times w)$
$f[1] = max(pre[1],pre[1+v] + w,pre[1+2\times v] + 2\times w,pre[1 + 3 \times v + 3\times w],\ldots,pre[1 + s \times v]+s\times w)$
$f[2] = max(pre[2],pre[2+v] + w,pre[2+2\times v] + 2\times w,pre[2 + 3 \times v + 3\times w],\ldots,pre[2 + s \times v]+s\times w)$
$$ \ldots\ldots $$
$f[j] = max(pre[j],pre[j+v] + w,pre[j+2\times v] + 2\times w,pre[j + 3 \times v + 3\times w],\ldots,pre[j + s \times v]+s\times w)$
所以说,单调队列每一次只需要维护$\{f[j], f[v+j], f[2\times v+j], f[3\times v+j], … , f[s\times v+j]\}$的一个合法区间内的最大值就可以了。
- 单调队列的模板
// 当前窗口最大值
hh = 0, tt = -1;
for(int i = 0; i < n; i++) {
if(hh <= tt && i - k + 1 > q[hh])
hh++;
while(hh <= tt && f[q[tt]] <= f[i])
tt--;
q[++tt] = i;
if(i >= k - 1) printf("%d ",f[q[hh]]);
}
而单调队列中,每一个下标位置$q[idx]$在本题中,所表示的意义为当前最大质量的背包的体积,计算的公式为:$j \times v + i$
那么,对应的$pre[idx]$位置的体积,他对于一个物品的价值的计算为:$(pre[idx] - i) / v \times w$
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 20100;
int f[N], pre[N], q[N];
int n,m;
int main() {
cin >> n >> m;
while(n --) {
memcpy(pre,f,sizeof f);
int v,w,s;
cin >> v >> w >> s;
for(int i = 0; i < v; i++) {
int hh = 0, tt = -1;
for(int j = i; j <= m; j += v) {
// 判断队头元素是否在当前区间内
if(hh <= tt && j - s * v > q[hh]) hh++;
// 去掉所有小于的区间
while(hh <= tt && pre[q[tt]] - (q[tt] - i) / v * w <= pre[j] - (j - i) / v * w) tt--;
// 更新
if(hh <= tt) f[j] = max(f[j], pre[q[hh]] + (j - q[hh]) / v * w);
q[++tt] = j;
}
}
}
cout << f[m] << endl;
return 0;
}