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;
}