高性能网站开发 书籍,微信h5游戏网站建设,做我的世界背景图的网站,把网站做到wordpress里面去题目链接#xff1a;题目页面
题目描述
题目描述
小明是一位科学家#xff0c;他需要参加一场重要的国际科学大会#xff0c;以展示自己的最新研究成果。他需要带一些研究材料#xff0c;但是他的行李箱空间有限。这些研究材料包括实验设备、文献资料和实验样本等等题目页面
题目描述
题目描述
小明是一位科学家他需要参加一场重要的国际科学大会以展示自己的最新研究成果。他需要带一些研究材料但是他的行李箱空间有限。这些研究材料包括实验设备、文献资料和实验样本等等它们各自占据不同的重量并且具有不同的价值。
小明的行李箱所能承担的总重量为 N问小明应该如何抉择才能携带最大价值的研究材料每种研究材料可以选择无数次并且可以重复选择。
输入描述
第一行包含两个整数NV分别表示研究材料的种类和行李空间
接下来包含 N 行每行两个整数 wi 和 vi代表第 i 种研究材料的重量和价值
输出描述
输出一个整数表示最大价值。
输入示例
4 5
1 2
2 4
3 4
4 5
输出示例
10
提示信息
第一种材料选择五次可以达到最大值。
数据范围
1 N 10000; 1 V 10000; 1 wi, vi 10^9.
文章讲解代码随想录
视频讲解带你学透完全背包问题 和 01背包有什么差别遍历顺序上有什么讲究_哔哩哔哩_bilibili
题解1动态规划
思路类似01背包问题完全背包问题也可以用动态规划法求解。完全背包和01背包的区别在于每个物品可以取任意次。
动态规划分析
dp 数组以及下标的含义dp[i][j] 表示从下标为0到 i 的物品里任意取放进容量为 j 的背包价值总和最大是多少。递推公式由于每个元素能取多次而 dp[i][j] 的状态依赖于当前元素一个也不取和再取1个当前元素。当前元素一个也不取即 dp[i - 1][j]再取一个当前元素即 dp[i][j - weight[i]] value[i]。即 dp[i][j] Math.max(dp[i - 1][j], dp[i][j - weight[i]] value[i])。dp 数组初始化dp[i][j] 的状态依赖于正上方和正左方的状态因此需要初始化第0行和第0列即 dp[0, j] 和 dp[i, 0]。dp[i, 0] 表示从下标为0到 i 的物品里任意取放进容量为 j 的背包价值总和最大自然是0。dp[0, j] 表示取或者不取下标为0的物品放进容量为 j 的背包j 小于 weight[0] 时价值总和最大为0大于等于 weight[0] 时为 k 倍value[0]k 取整数且最大满足 k * weight[0] j。遍历顺序dp[i][j] 的状态依赖于正上方和正左方的状态因此在填充 dp[i][j] 时它的正上方和同行的正左方需要填充。先遍历物品再遍历背包和先遍历背包再遍历物品这两种方式都可以。打印 dp 数组以如下输入为例 4 5 1 2 2 4 3 4 4 5 dp 数组为 [ [ 0, 2, 4, 6, 8, 10 ], [ 0, 2, 4, 6, 8, 10 ], [ 0, 2, 4, 6, 8, 10 ], [ 0, 2, 4, 6, 8, 10 ] ]。
const readline require(readline);
const rl readline.createInterface({input: process.stdin,output: process.stdout
});let num 1;
const inputs [];rl.on(line, (row) {inputs.push(row);if (inputs.length 1) {num parseInt(inputs[0]);}if (inputs.length num) {return;}const firstRow inputs[0].split( );const n parseInt(firstRow[0]);const w parseInt(firstRow[1]);const space [];const value [];for (let i 0; i n; i) {[space[i], value[i]] inputs[i 1].split( ).map(s parseInt(s));}// 定义 dp 数组const dp new Array(n).fill().map(() new Array(w 1).fill(0));// 初始化 dp 数组for (let j 0; j w 1; j) {let totalSpace 0;while (j - totalSpace space[0]) {totalSpace space[0];dp[0][j] value[0];}}// 先遍历物品再遍历背包for (let i 1; i n; i) {for (let j 1; j w 1; j) {if (j space[i]) {dp[i][j] dp[i - 1][j];} else {dp[i][j] Math.max(dp[i - 1][j], dp[i][j - space[i]] value[i]);}}}console.log(dp[n - 1][w]);
});
分析令物品数量为 n背包最大容量为 w则时间复杂度为 O(n * w)空间复杂度为 O(n * w)。
题解2动态规划优化
思路dp[i][j] 依赖于上一行正上方及本行正左方的状态与同一行后面的状态无关。可以想到填充某一行时将上一行内容覆盖到这一行上一行正上方即本身这样 dp[j] 的状态只依赖于前面的状态。
动态规划分析
dp 数组以及下标的含义dp[j]表示容量为j的背包所背的物品价值可以最大为dp[j]。递推公式dp[j] Math.max(dp[j], dp[j - weight[i]] value[i])。dp 数组初始化dp[0] 为0j 大于0时 dp[j] 依赖于上一轮的 dp[j] 和前面的状态为了取最大值后结果正确应该初始化为0。即全部初始化为0。遍历顺序dp[j] 的状态依赖于正左方的状态因此在填充 dp[j] 时它的正左方需要填充。先遍历物品再遍历背包和先遍历背包再遍历物品这两种方式都可以。打印 dp 数组以如下输入为例 4 5 1 2 2 4 3 4 4 5 每一层的 dp 数组为 [ 0, 2, 4, 6, 8, 10 ] [ 0, 2, 4, 6, 8, 10 ] [ 0, 2, 4, 6, 8, 10 ] [ 0, 2, 4, 6, 8, 10 ] 可以看到将每一层的 dp 数组结合起来和二维 dp 数组相同。
const readline require(readline);
const rl readline.createInterface({input: process.stdin,output: process.stdout
});let num 1;
const inputs [];rl.on(line, (row) {inputs.push(row);if (inputs.length 1) {num parseInt(inputs[0]);}if (inputs.length num) {return;}const firstRow inputs[0].split( );const n parseInt(firstRow[0]);const w parseInt(firstRow[1]);const space [];const value [];for (let i 0; i n; i) {[space[i], value[i]] inputs[i 1].split( ).map(s parseInt(s));}// 定义 dp 数组const dp new Array(w 1).fill(0);// 先遍历物品再遍历背包for (let i 0; i n; i) {// 正序遍历背包for (let j space[i]; j w; j) {dp[j] Math.max(dp[j], dp[j - space[i]] value[i]);}}console.log(dp[w]);
});
分析令物品数量为 n背包最大容量为 w则时间复杂度为 O(n * w)空间复杂度为 O(w)。
收获
学习使用动态规划法求解完全背包的理论知识。
