AcWing 7. 混合背包问题[二进制 + 单调队列]
原题链接
中等
作者:
旗木卡卡鸡
,
2022-05-10 10:49:07
,
所有人可见
,
阅读 201
算法1
(二进制优化)
C++ 代码
void fun_1(){
cin >> n >> m;
for(int i = 0; i < n; i++){
int v, w, s;
cin >> v >> w >> s;
if(!s){
for(int j = 0; j <= m; j++) if(j >= v) f[j] = max(f[j], f[j - v] + w);
}else{
if(s == -1) s = 1;
for(int k = 1; k <= s; k *= 2){
for(int j = m; j >= k * v; j--) f[j] = max(f[j], f[j - k * v] + k * w);
s -= k;
}
if(s){
for(int j = m; j >= s * v; j--) f[j] = max(f[j], f[j - s * v] + s * w);
}
}
}
cout << f[m] << endl;
}
算法2
(单调队列优化)
C++ 代码
void fun_2(){
cin >> n >> m;
for(int i = 0; i < n; i++){
int v, w, s;
cin >> v >> w >> s;
if(!s){
for(int j = 0; j <= m; j++) if(j >= v) f[j] = max(f[j], f[j - v] + w);
}else{
if(s == -1) s = 1;
memcpy(backup, f, sizeof(f));
for(int r = 0; r < v; r++){
int head = 0, tail = -1;
for(int k = 0; r + k * v <= m; k++){
if(head <= tail && k - dep[head] > s) head++;
if(head <= tail) f[r + v * k] = max(f[r + v * k], backup[r + dep[head] * v] + (k - dep[head]) * w);
while(head <= tail && backup[r + dep[tail] * v] - dep[tail] * w <= backup[r + k * v] - k * w) tail--;
dep[++tail] = k;
}
}
} // end else
} // end for
cout << f[m] << endl;
}