家具网站建设需求,织梦做信息类网站,汕头百度公司,顺德网站建设jinqiye题意描述#xff1a;
有 N 种物品和一个容量是 V 的背包。物品一共有三类#xff1a;第一类物品只能用1次#xff08;01背包#xff09;#xff1b;
第二类物品可以用无限次#xff08;完全背包#xff09;#xff1b;
第三类物品最多只能用 si 次#xff08;多重背包…题意描述
有 N 种物品和一个容量是 V 的背包。物品一共有三类第一类物品只能用1次01背包
第二类物品可以用无限次完全背包
第三类物品最多只能用 si 次多重背包每种体积是 vi价值是 wi。求解将哪些物品装入背包可使物品体积总和不超过背包容量且价值总和最大。
输出最大价值。输入格式
第一行两个整数NV用空格隔开分别表示物品种数和背包容积。接下来有 N 行每行三个整数 vi,wi,si用空格隔开分别表示第 i 种物品的体积、价值和数量。si−1 表示第 i 种物品只能用1次
si0 表示第 i 种物品可以用无限次
si0 表示第 i 种物品可以使用 si 次输出格式
输出一个整数表示最大价值。数据范围
0N,V≤1000
0vi,wi≤1000
−1≤si≤1000示例 4 5 1 2 -1 2 4 1 3 4 0 4 5 2 8 解题思路 Alice: 笑死这题可以直接改一下输入改成多重背包就可以了 Bob: 对01背包的物品数量就是 1数量 1 也是多重背包的一种。完全背包的话背包体积是有限的能装进去的物品数量也是有限的直接算一下然后上取整就得了。其他代码不用改直接用单调队列优化的肯定能过。 代码
转换成多重背包 单调队列求解
const fs require(fs);
let buffer ;process.stdin.on(readable, () {const chunk process.stdin.read();if (chunk) {buffer chunk.toString()}
});// 输入的字符串转换为数字
const convert (inputString) {const list [];inputString.split(\n).forEach((line) {const tokens line.split( );list.push(tokens.map(num parseInt(num, 10)));});return list;
}// 批量调用
const batchCall (list, solve) {// 划分数据const data [];let countAndVolumIndex 0;while(countAndVolumIndex list.length) {const [count, volum] list[countAndVolumIndex];// 转化成多重背包问题data.push({volum: volum,count: count,volumAndWeightAndCount: list.slice(countAndVolumIndex 1, countAndVolumIndex 1 count).map(item {const [v, w, s] item;let normalizedS s;if(s -1) {normalizedS 1;}if(s 0) {normalizedS Math.ceil(volum / v);}return [v, w, normalizedS];}),});countAndVolumIndex count 1;}data.forEach(item {if(solve item item.count item.volum) {solve(item.count, item.volum, item.volumAndWeightAndCount);}});
}const solve (count, maxVolum, volumAndWeightAndCount) {// 单调队列优化方法const dp new Array(maxVolum 10).fill(0);// 对于每种物品 for (let i0; icount; i) {// 状态压缩const lastRowDp [...dp];// 取出第 i 种物品的体积价值数量const [vi, wi, si] volumAndWeightAndCount[i];// 对于每种可能剩余的体积0,1,2, ... vi-1 for (let r0; rvi; r) {// 单调队列求解每种可能的最大值滑动窗口大小是math.min (si, maxVolum / vi) 下取整// 0 0v, 0 1v, 0 2v ... 0 kv 的数组中滑动每次一步// 最大价值对应的体积的单调队列双端队列queue[0] 是合法的最大价值对应的体积const queue [];for(let jr; jmaxVolum; jvi) {// 维护队首// i 物品的体积超了while(queue.length j-queue[0] vi*si) {queue.shift();}// 维护队尾while(queue.length lastRowDp[queue[queue.length-1]] (j - queue[queue.length-1]) /vi * wi lastRowDp[j]) {queue.pop();}// 入队queue.push(j);// 更新 dpdp[j] lastRowDp[queue[0]] (j-queue[0]) / vi * wi;}}}console.log(dp[maxVolum]);
}process.stdin.on(end, function() {batchCall(convert(buffer), solve)
});参考
题目链接
