题目描述
有 N
种物品和一个容量是 V
的背包。
第 i
种物品最多有 si
件,每件体积是 vi
,价值是 wi
。
求解将哪些物品装入背包,可使物品体积总和不超过背包容量,且价值总和最大。
输出最大价值。
输入格式
第一行两个整数,N,V
(0<N≤1000
, 0<V≤20000)
,用空格隔开,分别表示物品种数和背包容积。
接下来有 N
行,每行三个整数 vi,wi,si
,用空格隔开,分别表示第 i
种物品的体积、价值和数量。
输出格式
输出一个整数,表示最大价值。
数据范围
0<N≤1000
0<V≤20000
0<vi,wi,si≤20000
提示
本题考查多重背包的单调队列优化方法。
输入样例
4 5
1 2 3
2 4 1
3 4 3
4 5 2
输出样例:
10
与完全背包类似,固定i(选前i个物品),先来枚举一遍f[i][j - kv]看看
f[i][j] = max(f[i-1][j],f[i-1][j-v]+w,f[i-1][j-2v]+2w ··· f[i-1][j-sv]+sw)
f[i][j] = max( f[i-1][j-v], f[i-1][j-2v]+w,f[i-1][j-3v]+2w···f[i-1][j-sv]+(s-1)w)+f[i-1][j-(s+1)v]+sw)
···
其实是用单调队列求
f[i-1][r],f[i-1][r+v],···f[i-1][j]
这个序列中的的长度为s的滑动窗口的最大值
但是,因为上下的表达式其实不完全相等,每行相差一个w,需要加上一个偏置
我们在滑动窗口比较是否出队时,不直接比较f[i-1][tt]和f[i-1][k]的值,而是比较他们加上了偏置后的值
对于f[r + kv]我们给它加上-kw的偏置而不是w,这样可以保证在之后的每次(k变化时)比较这个偏置都是有效的
代码如下,其中用了滚动数组去掉了第一维,因为每次第一重循环中我们总是只用到了前一层的结果
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 20010;
int f[N], g[N], q[N], v, w, s, n, m;
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; i ++ )
{
cin >> v >> w >> s;
memcpy(g, f, sizeof f);
for (int j = 0; j < v; j ++)
{
int tt = -1, hh = 0;
for (int k = j; k <= m; k += v)
{
if (hh <= tt && k - q[hh] > s * v) hh ++;
/*其实,这里也可以理解为g[q[tt]] + (k - q[tt]) / v * w <= g[k]),就是说每次窗口移动一次序列中的值都会比上一次的值多w,k - q[tt]就是我当前的窗口应该比队头的窗口多出多少个w
*/
while (hh <= tt && g[q[tt]] - (q[tt] - j) / v * w <= g[k] - (k - j) / v * w) tt -- ;
q[++ tt] = k;
f[k] = g[q[hh]] + (k - q[hh]) / v * w;
}
}
}
cout << f[m] << endl;
return 0;
}