【卡码网】0-1背包问题 46. 携带研究材料——代码随想录算法训练营Day41

本文主要是介绍【卡码网】0-1背包问题 46. 携带研究材料——代码随想录算法训练营Day41,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目链接:46. 携带研究材料

题目描述

时间限制:5.000S  空间限制:128MB

题目描述

小明是一位科学家,他需要参加一场重要的国际科学大会,以展示自己的最新研究成果。他需要带一些研究材料,但是他的行李箱空间有限。这些研究材料包括实验设备、文献资料和实验样本等等,它们各自占据不同的空间,并且具有不同的价值。 

小明的行李空间为 N,问小明应该如何抉择,才能携带最大价值的研究材料,每种研究材料只能选择一次,并且只有选与不选两种选择,不能进行切割。

输入描述

第一行包含两个正整数,第一个整数 M 代表研究材料的种类,第二个正整数 N,代表小明的行李空间。

第二行包含 M 个正整数,代表每种研究材料的所占空间。 

第三行包含 M 个正整数,代表每种研究材料的价值。

输出描述

输出一个整数,代表小明能够携带的研究材料的最大价值。

输入示例
6 1
2 2 3 1 5 2
2 3 1 5 4 3
输出示例
5
提示信息

小明能够携带 6 种研究材料,但是行李空间只有 1,而占用空间为 1 的研究材料价值为 5,所以最终答案输出 5。 

数据范围:
1 <= N <= 5000
1 <= M <= 5000
研究材料占用空间和价值都小于等于 1000

文章讲解:代码随想录

视频讲解:带你学透0-1背包问题!| 关于背包问题,你不清楚的地方,这里都讲了!| 动态规划经典问题 | 数据结构与算法_哔哩哔哩_bilibili

题解1:回溯法

思路:使用回溯法暴力遍历所有物品是否放入的所有情况,找出最大价值。

const readline = require('readline');
const rl = readline.createInterface({input: process.stdin,output: process.stdout
});const num = 3;
const inputs = [];rl.on("line", (row) => {inputs.push(row);if (inputs.length < num) {return;}const firstRow = inputs[0].split(' ');const n = parseInt(firstRow[0]);const w = parseInt(firstRow[1]);const space = inputs[1].split(" ").map(s => parseInt(s));const value = inputs[2].split(" ").map(s => parseInt(s));let res = 0;const path = [];const backtracking = function (start, totalSpace, totalValue) {if (totalValue > res) {res = totalValue;}for (let i = start; i < n; i++) {// 可以将下标为 i 的物品放入背包if (totalSpace + space[i] <= w) {path.push(i);backtracking(i + 1, totalSpace + space[i], totalValue + value[i]);path.pop();}}};backtracking(0, 0, 0);console.log(res);
});

分析:令 n 为物品数量,时间复杂度为 O(2 ^ n),空间复杂度为 O(logn)。这个解法时间复杂度过高,为指数级,不推荐使用。

题解2:动态规划

思路:最经典解01背包问题的方法是动态规划法。

注意:此题为 ACM 模式,需要自己在代码中读取输入,打印输出。

动态规划分析:

  • dp 数组以及下标的含义:dp[i][j] 表示从下标为0到 i 的物品里任意取,放进容量为 j 的背包,价值总和最大是多少。
  • 递推公式:dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][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] 时为 value[0]。
  • 遍历顺序:dp[i][j] 的状态依赖于正上方和左上方的状态,因此在填充 dp[i][j] 时,它的正上方和上一行的左上方需要填充。先遍历物品再遍历背包和先遍历背包再遍历物品这两种方式都可以。
  • 打印 dp 数组:以如下输入为例

5 6
1 2 3 4 5
2 4 4 5 6

dp 数组为 [ [ 0, 2, 2, 2, 2, 2, 2 ], [ 0, 2, 4, 6, 6, 6, 6 ], [0, 2,  4, 6, 6, 8, 10 ], [ 0, 2,  4, 6, 6, 8, 10 ], [ 0, 2,  4, 6, 6, 8, 10 ] ]。

const readline = require('readline');
const rl = readline.createInterface({input: process.stdin,output: process.stdout
});const num = 3;
const inputs = [];rl.on("line", (row) => {inputs.push(row);if (inputs.length < num) {return;}const firstRow = inputs[0].split(' ');const n = parseInt(firstRow[0]);const w = parseInt(firstRow[1]);const space = inputs[1].split(" ").map(s => parseInt(s));const value = inputs[2].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++) {if (j >= 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 - 1][j - space[i]] + value[i]);}}}console.log(dp[n - 1][w]);
});

分析:令物品数量为 n,背包最大容量为 w,则时间复杂度为 O(n * w),空间复杂度为 O(n * w)。

题解3:动态规划优化

思路: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] 为0,j 大于0时 dp[j] 依赖于上一轮的 dp[j] 和前面的状态,为了取最大值后结果正确,应该初始化为0。即全部初始化为0。
  • 遍历顺序:先从前往后遍历物品,再从后往前遍历背包。
  • 打印 dp 数组:以如下输入为例

5 6
1 2 3 4 5
2 4 4 5 6

每一层的 dp 数组为

[0, 2, 2, 2, 2, 2, 2]
[0, 2, 4, 6, 6, 6, 6]
[0, 2,  4, 6, 6, 8, 10]
[0, 2,  4, 6, 6, 8, 10]
[0, 2,  4, 6, 6, 8, 10]

可以看到,将每一层的 dp 数组结合起来,和二维 dp 数组相同。

const readline = require('readline');
const rl = readline.createInterface({input: process.stdin,output: process.stdout
});const num = 3;
const inputs = [];rl.on("line", (row) => {inputs.push(row);if (inputs.length < num) {return;}const firstRow = inputs[0].split(' ');const n = parseInt(firstRow[0]);const w = parseInt(firstRow[1]);const space = inputs[1].split(" ").map(s => parseInt(s));const value = inputs[2].split(" ").map(s => parseInt(s));// 定义 dp 数组const dp = new Array(w + 1).fill(0);// 先遍历物品,再遍历背包for (let i = 0; i < n; i++) {// 倒序遍历背包for (let j = w; j >= space[i]; j--) {dp[j] = Math.max(dp[j], dp[j - space[i]] + value[i]);}}console.log(dp[w]);
});

分析:令物品数量为 n,背包最大容量为 w,则时间复杂度为 O(n * w),空间复杂度为 O(w)。

收获

学习01背包问题的动态规划解法。

这篇关于【卡码网】0-1背包问题 46. 携带研究材料——代码随想录算法训练营Day41的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/744514

相关文章

Python实现MQTT通信的示例代码

《Python实现MQTT通信的示例代码》本文主要介绍了Python实现MQTT通信的示例代码,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一... 目录1. 安装paho-mqtt库‌2. 搭建MQTT代理服务器(Broker)‌‌3. pytho

Spring的RedisTemplate的json反序列泛型丢失问题解决

《Spring的RedisTemplate的json反序列泛型丢失问题解决》本文主要介绍了SpringRedisTemplate中使用JSON序列化时泛型信息丢失的问题及其提出三种解决方案,可以根据性... 目录背景解决方案方案一方案二方案三总结背景在使用RedisTemplate操作redis时我们针对

MySQL进行数据库审计的详细步骤和示例代码

《MySQL进行数据库审计的详细步骤和示例代码》数据库审计通过触发器、内置功能及第三方工具记录和监控数据库活动,确保安全、完整与合规,Java代码实现自动化日志记录,整合分析系统提升监控效率,本文给大... 目录一、数据库审计的基本概念二、使用触发器进行数据库审计1. 创建审计表2. 创建触发器三、Java

Kotlin Map映射转换问题小结

《KotlinMap映射转换问题小结》文章介绍了Kotlin集合转换的多种方法,包括map(一对一转换)、mapIndexed(带索引)、mapNotNull(过滤null)、mapKeys/map... 目录Kotlin 集合转换:map、mapIndexed、mapNotNull、mapKeys、map

nginx中端口无权限的问题解决

《nginx中端口无权限的问题解决》当Nginx日志报错bind()to80failed(13:Permissiondenied)时,这通常是由于权限不足导致Nginx无法绑定到80端口,下面就来... 目录一、问题原因分析二、解决方案1. 以 root 权限运行 Nginx(不推荐)2. 为 Nginx

解决1093 - You can‘t specify target table报错问题及原因分析

《解决1093-Youcan‘tspecifytargettable报错问题及原因分析》MySQL1093错误因UPDATE/DELETE语句的FROM子句直接引用目标表或嵌套子查询导致,... 目录报js错原因分析具体原因解决办法方法一:使用临时表方法二:使用JOIN方法三:使用EXISTS示例总结报错原

Windows环境下解决Matplotlib中文字体显示问题的详细教程

《Windows环境下解决Matplotlib中文字体显示问题的详细教程》本文详细介绍了在Windows下解决Matplotlib中文显示问题的方法,包括安装字体、更新缓存、配置文件设置及编码調整,并... 目录引言问题分析解决方案详解1. 检查系统已安装字体2. 手动添加中文字体(以SimHei为例)步骤

SpringSecurity整合redission序列化问题小结(最新整理)

《SpringSecurity整合redission序列化问题小结(最新整理)》文章详解SpringSecurity整合Redisson时的序列化问题,指出需排除官方Jackson依赖,通过自定义反序... 目录1. 前言2. Redission配置2.1 RedissonProperties2.2 Red

nginx 负载均衡配置及如何解决重复登录问题

《nginx负载均衡配置及如何解决重复登录问题》文章详解Nginx源码安装与Docker部署,介绍四层/七层代理区别及负载均衡策略,通过ip_hash解决重复登录问题,对nginx负载均衡配置及如何... 目录一:源码安装:1.配置编译参数2.编译3.编译安装 二,四层代理和七层代理区别1.二者混合使用举例

怎样通过分析GC日志来定位Java进程的内存问题

《怎样通过分析GC日志来定位Java进程的内存问题》:本文主要介绍怎样通过分析GC日志来定位Java进程的内存问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录一、GC 日志基础配置1. 启用详细 GC 日志2. 不同收集器的日志格式二、关键指标与分析维度1.