AcWing 6. 多重背包问题 III-JavaScript
原题链接
困难
作者:
semicloud
,
2024-03-13 18:11:23
,
所有人可见
,
阅读 11
const fs = require('fs');
const it = fs.readFileSync(0, 'utf-8').split('\n')[Symbol.iterator]();
const readNums = () => it.next().value.split(' ').map((x) => parseInt(x));
const [n, m] = readNums();
let t = n;
// 体积、价值、数量数组下标从1开始
const [v, w, s] = [[0], [0], [0]];
while (t--) {
const [vi, wi, si] = readNums();
v.push(vi);
w.push(wi);
s.push(si);
}
const f = Array(n + 1).fill(0).map((x) => Array(m + 1).fill(0));
// 单调队列
const q = Array(m + 1).fill(0);
// 单调队列的队头队尾,初始状态下队空,即hh>tt
let [hh, tt] = [0, -1];
for (let i = 1; i <= n; ++i) {
for (let mod = 0; mod <= Math.min(m, v[i] - 1); ++mod) {
[hh, tt] = [0, -1]; // 单调队列清空
// 处理每个分组
for (let j = mod; j <= m; j += v[i]) {
// 队尾元素补足后的价值,或者说相对于j的价值:
while (hh <= tt && f[i - 1][q[tt]] + (j - q[tt]) / v[i] * w[i] <=
f[i - 1][j]) tt--;
q[++tt] = j;
// 队头出队条件
if (hh <= tt && q[hh] === j - v[i] * (s[i] + 1)) hh++;
f[i][j] = f[i - 1][q[hh]] + (j - q[hh]) / v[i] * w[i];
}
}
}
console.log(f[n][m]);