AcWing
6. 多重背包问题III
接多重背包问题II,二进制优化的时间复杂度为$O(NMlogM)$,如果想继续优化,可以使用单调队列,时间复杂度将降低到$O(NM)$.
二进制优化将多重背包建模为拆分+01背包,单调队列优化将多重背包建模为特殊的分组背包问题,每个组内是{0*item_i, 1*item_i, 2*item_i, …, s[i]*item_i},在每个分组中只能取一件物品。
考虑前n
种(组)物品,在背包容量为m
的时候,状态转移方程为:
f[n][m] = max{f[n-1][m], f[n-1][m-v[i]] + w[i], ..., f[n-1][m-k[i]] + k*w[i]}
当遍历到某一种物品n
,考虑其对应的容量m
的转移情况,令r∈[0, v[i]-1]
,表示m
对v[i]
的余数,对某一确定的余数r
,总能确定一组容量r, r+v[i], r+2v[i], ...
,现在考虑这组容量下的状态转移情况:
f[n][r] = f[n-1][r]
f[n][r+v[i]] = max{f[n-1][r+v[i]], f[n-1][r]+w[i]}
f[n][r+2v[i]] = max{f[n-1][r+2v[i]], f[n-1][r+v[i]]+w[i], f[n-1][r]+2w[i]}
......
f[n][r+kv[i]] = max{f[n-1][r+kv[i]], f[n-1][r+(k-1)v[i]]+w[i], ..., f[n-1][r]+kw[i]}
......
当k > s[i]
,此时情况有所不同:f[n][r+kv[i]] = max{f[n-1][r+kv[i]], f[n-1][r+(k-1)v[i]]+w[i], ..., f[n-1][r+(k-s[i])v[i]]+s[i]w[i]}
观察可知,通过上一行的结果,总是能简化下一行的计算。对于普遍的情况,可以使用单调递减的单调队列来维护区间内的最大值。
小技巧:多开一个dp数组g[M]
,每次存上个物品结束时的状态,这样就不需要考虑01背包被污染的问题。
#include <bits/stdc++.h>
using namespace std;
int n, m;
const int N = 1010, M = 20010;
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 f);
for(int j = 0; j <= v[i] - 1; j++){
int hh = 0, tt = -1;
for(int k = j; k <= m; k += v[i]){
if(hh <= tt && k - q[hh] > s[i] * v[i]) hh++;
while(hh <= tt && g[q[tt]] + (k - q[tt]) / v[i] * w[i] <= g[k]) tt--;
q[++tt] = k;
f[k] = g[q[hh]] + (k - q[hh]) / v[i] * w[i];
}
}
}
cout << f[m] << endl;
return 0;
}