AcWing
7. 混合背包问题
混合背包问题是说，对于每一种物品，其数量可能是1, INF, 或者s[i]。对于这种问题，只需要分别判断物品的类型，分别对特定的类型做特定处理即可。对于题目所给的数据范围，多重背包的物品只需要做二进制优化即可(单调队列优化更好)。其中，数量为1的物品也可以看作s[i] == 1，当作多重背包一起处理。
二进制优化写法：
#include <bits/stdc++.h>
using namespace std;
int n, m;
const int N = 1010, M = 1010;
int v[N], w[N], s[N];
int f[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++){
if(s[i] == -1){ // 01
for(int j = m; j >= v[i]; j--) f[j] = max(f[j], f[j - v[i]] + w[i]);
}
else if(s[i] == 0){ // inf
for(int j = v[i]; j <= m; j++) f[j] = max(f[j], f[j - v[i]] + w[i]);
}
else{ // multi
for(int k = 1; k <= s[i]; k *= 2){
for(int j = m; j >= k * v[i]; j--) f[j] = max(f[j], f[j - k * v[i]] + k * w[i]);
s[i] -= k;
}
if(s[i])
for(int j = m; j >= s[i] * v[i]; j--) f[j] = max(f[j], f[j - s[i] * v[i]] + s[i] * w[i]);
}
}
cout << f[m] << endl;
return 0;
}
单调队列优化写法：
#include <bits/stdc++.h>
using namespace std;
int n, m;
const int N = 1010, M = 1010;
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++){
if(s[i] == -1){ // 01
for(int j = m; j >= v[i]; j--) f[j] = max(f[j], f[j - v[i]] + w[i]);
}
else if(s[i] == 0){ // inf
for(int j = v[i]; j <= m; j++) f[j] = max(f[j], f[j - v[i]] + w[i]);
}
else{ // multi
memcpy(g, f, sizeof f);
for(int r = 0; r <= v[i] - 1; r++){
int hh = 0, tt = -1;
for(int j = r; j <= m; j += v[i]){
if(hh <= tt && j - q[hh] > s[i] * v[i]) hh++;
while(hh <= tt && g[j] >= g[q[tt]] + (j - q[tt]) / v[i] * w[i]) tt--;
q[++tt] = j;
f[j] = g[q[hh]] + (j - q[hh]) / v[i] * w[i];
}
}
}
}
cout << f[m] << endl;
return 0;
}