常州网站建设策划,注册500万公司实缴多少钱,网站建设 营业执照 经营范围,山东省住建厅官网二建查询题意描述#xff1a;
有 N 种物品和一个容量是 V 的背包。第 i 种物品最多有 si 件#xff0c;每件体积是 vi#xff0c;价值是 wi。求解将哪些物品装入背包#xff0c;可使物品体积总和不超过背包容量#xff0c;且价值总和最大。
输出最大价值。输入格式
第一行两个整数…题意描述
有 N 种物品和一个容量是 V 的背包。第 i 种物品最多有 si 件每件体积是 vi价值是 wi。求解将哪些物品装入背包可使物品体积总和不超过背包容量且价值总和最大。
输出最大价值。输入格式
第一行两个整数NV (0N≤1000, 0V≤20000)用空格隔开分别表示物品种数和背包容积。接下来有 N 行每行三个整数 vi,wi,si用空格隔开分别表示第 i 种物品的体积、价值和数量。输出格式
输出一个整数表示最大价值。多重背包的问题根据数据范围的大小划分为了三个难度层次分别对应三种解法。对应的数据范围分别是
暴力求解
0N,V≤100
0vi,wi,si≤100二进制优化
0N≤1000
0V≤2000
0vi,wi,si≤2000单调队列优化
0N≤1000
0V≤20000
0vi,wi,si≤20000示例 4 5 1 2 3 2 4 1 3 4 3 4 5 2 10 解题思路 Alice: 这是一道题拆成了三道题 这题这么难 Bob: 丰俭由人 Alice: 多重背包和 01 背包的区别就是每类物品有了数量的限制01 背包是只能选或者不选完全背包是由无数种可以选01 背包是有 k 种可以选。 Bob: 是的那直接改一下状态转移公式得了直接按照完全背包的方式换一下最内层的状态转移好了dp[j] max(dp[j], dp[j-vi * k] wi * k) k 取值 0,1,2,3 … Alice: 为啥要按照完全背包从最大体积开始求解 Bob: 看状态转移方程我们还用一维度的 dp 数组的话对于第 i 个物品还需要用到第 i-1 个物品的 j-vi * k 的状态从最大体积往小了计算才是对的。 Alice: 这个理解起来还不太难。 Bob 是的这里可以关注一下计算量暴力去算实际上是 O^3 的数据范围都是 100最大也就是 10^6这样不会超时的。 Alice: 二进制优化讲的是啥 Bob: 二进制优化的前提是把多重背包转换成 01 背包问题但是转换的方式有很多种二进制优化是其中一种的优化方法。举个例子第 0 种物品有 7 个我们该如何拆分呢拆成 7 个1 每个体积和价值都是 v0w0。这样的计算量大概O^2 也就是双重循环1000 * 2000 * 2000 大概 2* 10^9, 1s 的时间限制大概能完成10^6~10^7这样会超时的。 Alice: 是的直接拆拆出来的物品数量太多了 Bob: 这样其实就转换成了拆分的问题把 7 拆成若干个数字且这些数字能组成 0-7 的所有数字。 Alice: 哦哦就是二进制啊二进制是能够表达所有整数的0到7也就是2^1 , 2^1, 2^2 这些。然后其实就是二进制的表示一样7 就是 111对应到三个物品就是全选 Bob: 对但是还有一个问题如果你的数字是 8 呢拆成 12, 48 那样的话就有可能选出 12 4 8 15 的选择但是原来最多也就是 8个。 Alice: 可以这样子8 的数字就用 7 的那套剩下的差值额外补齐0-7 的范围再加个 1所能表达的范围就是 0-8。 Bob: 应该就是这样然后具体拆分的时候还可以直接从 1,2,4 累乘然后不断地减下来最后剩下的额外加一套。这样应该比较方便而且很快。 Alicenice拆外之后直接用 01 背包就行了。这样算的计算量应该是 log 2000 * 1000 * 2000 2.2 * 10^7 应该没问题啦。 Bob单调队列优化呢 Alice: 这个看起来很麻烦的样子是啊这个需要先知道单调队列是啥。可以先看一下 这篇文章 Bob单调队列优化的思路大概是这样的还得从完全背包的递推公式讲起考虑第 i 种物品 dp[j] max(dp[j], dp[j-vi * k] wi * k) k 取值 0,1,2,3 …。这里实际的计算过程是什么样的呢j-vi*k 减到最后无论 j 的取值是啥一定剩下的是 vi 的各种余数1,2,3 … vi-1然后从 1v12v13v … 的状态转移计算过程会相互影响而 2v22v23v 会相互影响两个余数之间的计算过程互相不影响这样我们就能把对 i 物品的计算划分为互相独立的 vi-1 个然后单独计算。 Alice: 然后的拆分成 多个计算过程就能变快 并行处理吗 Bob: 然后就是难以理解的地方了我先举个例子吧假设背包体积是 100 第 i 种物品的体积是 5价值是 4数量是 3考虑第 i 个物品时候的状态的计算dp[j] max(dp[j- 5*0] 4*0, dp[j- 5*1] 4*1, dp[j-5*2] 4*2), dp[j - 5*3] 4*3具体的计算过程从底向上就是 求 dp[0 5*0], dp[0 5*1] 4*1, dp[0 5*2] 4*2, dp[0 5*3] 4*3 之间的最大值然后再根据放 1 个2个3个求出 dp[020] 而 dp[120] 看的是 dp[1 5*0] 4*0, dp[1 5*1] 4*1, dp[1 5*2] 4*2, dp[1 5*3] 4*3 的最大值。明白了吗 ? 0,1,2 在这里就是不同的计算序列每个计算序列都要根据 4 的滑动窗口求前面的最大值然后再计算当前的最大值。 Alice: 滑动窗口就在这呢原来是对第 i 种物品的体积余数的每个计算序列里面滑动滑动窗口的大小就是物品的最大数量。 Bob: 其实滑动窗口的大小不一定是物品的最大数量k 的实际取值范围是 math.min (si 1, maxVolum / vi)不过这个可以在代码层直接实现掉可以暂时认为是最大数量不影响理解。 Alice: 然后单调队列里面维护的时候什么呢 队首和队尾都是怎么维护的呢 Bob: 单调队列里面维护的是当前窗口里面最大价值所对应的体积这样我们应该能够比较轻松的写出 dp[j] 的更新dp[j] lastRowDp[queue[0]] (j - queue[0]) / vi * wi想一下queue[0] 里面是当前窗口的最大价值对应的体积我们在这个体积之上更新 dp[j]。队首的维护其实还是窗口的大小只不过这里窗口的大小是通过体积的计算来校验的。 Alice: 这些都还好理解那队尾的维护呢 我记得滑动窗口最大值里面是直接计算窗口里面的数字之和这里应该不是吧。 Bob: 确实不是这里还有点不太好理解。这里还是按照最大价值来计算的只是比较的是第 i-1 个物品对应的体积和 第 i 个物品对应的体积所能给 dp[j] 带来的价值收益。要知道我们在 queue[0] 队首的位置维护的是在窗口中能给 dp[j] 带来最大价值的体积而单调队列的维护正式通过队首和队尾维护的所以队尾的维护逻辑实际和 dp[j] 的更新逻辑是一致的。 Alice: 更新逻辑是一致的 我好像有点明白了。还有一些细节问题滑动窗口的大小不定是怎么实现的 Bob: 这个好说你从余数 r 开始r 就是 r 0 * vi 然后每次给 r vi让 r 不要超过最大体积就可以了。 Alice: 这题真难。 Bob这题真难我看别人的题解看了半天才明白滑动窗口在哪滑呢看别人代码看了半天单调队列维护的代码都快背下来了也没看明白怎么维护的还是得实际举个例子。 Alice: 还有一个小问题这里为啥不能把状态压缩成一个一位数组为啥还要一个 lastRowDp 呢 Bob简单第 i 个物品的 dp[j] 的更新需要依赖于体积 j 的前 si 个状态如果直接用 dp[j - vi]那用的就是更新过的值了就不是 i-1 个物品的状态了。 代码
暴力
const solve (count, maxVolum, volumAndWeight) {const dp new Array(maxVolum 1).fill(0);for(let i0; icount; i){// 第 i 个物品的体积和价值const [ivolum, iweight, itotal] volumAndWeight[i];for(let jmaxVolum; jivolum; --j) {const candiantes [];for(let k0; kitotal; k) {j - ivolum * k 0 candiantes.push(dp[j - ivolum * k] k * iweight);}dp[j] Math.max(...candiantes);}}console.log(dp[maxVolum]);
}二进制优化
const solve (count, maxVolum, volumAndWeightAndCount) {// 二进制拆分为 01 背包const volumnAndWeight [];volumAndWeightAndCount.forEach(item {let [v, w, s] item;for (let k1; k s; k*2) {s - k;volumnAndWeight.push([k*v, k*w]);}if(s 0) {volumnAndWeight.push([s*v, s*w]);}});// 01 背包解法const dp new Array(maxVolum 1).fill(0);for(let i0; ivolumnAndWeight.length; i){// 第 i 个物品的体积和价值const [ivolum, iweight] volumnAndWeight[i];for(let jmaxVolum; jivolum; --j) {dp[j] Math.max(dp[j], dp[j - ivolum] iweight);}}console.log(dp[maxVolum]);
}单调队列优化
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)});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 的数组中滑动每次一步// 最大价值对应的体积的单调队列双端队列const queue [];for(let jr; jmaxVolum; jvi) {// 维护队首// i 物品的体积超了注意这里是大于而不是大于等于要把 r0*vi也包括进来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)
});参考
题目链接-多重背包1题目链接-多重背包2题目链接-多重背包3参考题解
