KamaCoder 46. 携带研究材料(第六期模拟笔试)
题目描述
小明是一位科学家,他需要参加一场重要的国际科学大会,以展示自己的最新研究成果。他需要带一些研究材料,但是他的行李箱空间有限。这些研究材料包括实验设备、文献资料和实验样本等等,它们各自占据不同的空间,并且具有不同的价值。
小明的行李空间为 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 背包问题。可以采用动态规划解决。dp[ i ][ j ] 表示 0~ i 号物品放入 容量为 j 的背包时的最大价值。
确定递推公式:dp[ i ][ j ] 有两个来源:
- 容量为 j 的背包不能装下 i 号物品,则容量为 j 的背包中所装的物品为 0 ~ i-1 号,其最大价值为 dp [ i -1 ][ j ]
- 容量为 j 的背包能装下 i 号物品,则容量为 j 的背包 此时所能装下的价值为 dp[ i-1 ][ j - weight [ i ] ] + value[ i ]
故 dp[ i ][ j ] = Math.max(dp [ i -1 ][ j ] ,dp[ i-1 ][ j - weight [ i ] ] + value[ i ]);
初始化:当容量 j = 0 时 dp[ i ][ 0 ] 肯定为 0;当 i = 0,即只将 0 号物品装入 背包时,如果背包的容量 j < weight [ 0 ],则此时装不进背包,背包中的价值为 0,当 背包的容量 j >= weight[ 0] 时,这时可以将 0 号物品装入背包,背包的价值为 value[ 0 ]。
遍历顺序:从 i = 1,j = 1 开始从左往右,从上往下遍历,因为从递推公式来看, dp[ i ][ j ] 依赖其左上方 的 dp 值。
代码:
import java.util.*;
class Main{public static void main(String [] args){Scanner scan = new Scanner(System.in);int m = scan.nextInt();int n = scan.nextInt(); //背包大小int[] weight = new int[m];int[] value = new int[m];for(int i=0;i<m;i++){weight[i] = scan.nextInt();}for(int i=0;i<m;i++){value[i] = scan.nextInt();}// dp[i][j] 表示 0到 i 号物品 放在容量为 j 的背包里面的最大价值int [][] dp = new int[m][n+1];// 对 dp 进行初始化for(int j=weight[0];j<n+1;j++){dp[0][j] = value[0];}for(int i=1;i<m;i++){for(int j=1;j<n+1;j++){dp[i][j] = Math.max(dp[i-1][j],(j-weight[i]>=0)?dp[i-1][j-weight[i]]+value[i]:-1);}}System.out.println(dp[m-1][n]);}
}
参考:代码随想录
相关文章:
KamaCoder 46. 携带研究材料(第六期模拟笔试)
题目描述 小明是一位科学家,他需要参加一场重要的国际科学大会,以展示自己的最新研究成果。他需要带一些研究材料,但是他的行李箱空间有限。这些研究材料包括实验设备、文献资料和实验样本等等,它们各自占据不同的空间࿰…...
MySQL的基本操作(超详细)
👨💻作者简介:👨🏻🎓告别,今天 📔高质量专栏 :☕java趣味之旅 📔(零基础)专栏:MSQL数据库 欢迎🙏点赞&…...
自动驾驶之心规划控制笔记
Search-based Path Planning Methods Path Finding Problem 一般来说指标有距离,耗费时间,能量,或者多目标。 左图是拓扑地图,蓝色的点就是顶点,绿色的线是连接关系。最后得到的是一个从哪里走的一个最优,并非精细解。 右图是栅格地图,这个搜索出来的是在相对分辨率比…...
Linux中部署Java jar 包 shell 脚本
Linux中部署Java jar 包 shell 脚本 #!/bin/bash set -e# 基础 # export JAVA_HOME/work/programs/jdk/jdk1.8.0_181 # export PATHPATH$PATH:$JAVA_HOME/bin # export CLASSPATH$JAVA_HOME/jre/lib/rt.jar:$JAVA_HOME/lib/dt.jar:$JAVA_HOME/lib/tools.jarDATE$(date %Y%m%d%…...
auto.js v1.4.4 实现自动打卡
一、使用场景 所在公司的打卡软件可以单独变成一个可以点击的APP,所以只需要实现以下步骤: 自动解锁屏幕返回主屏幕并打卡锁定屏幕需要的环境: 手机端下载并且安装 auto.js v4.1.1 PC端VS安装对应的插件学习资料 B站学习资料 对应 第三期&am…...
【Linux实验室】NFS、DHCP的搭建
NFS、DHCP的搭建 1、nfs服务搭建及测试什么是NFS?环境准备服务端机器安装nfs-utils和rpcbind包启动NFS服务创建/data/NFSdata目录,配置nfs文件启动服务挂载测试在服务端在共享目录下创建文件测试在客户端在共享目录下创建文件 2、dhcp服务搭建及测试什么…...
Samba 总是需要输入网络凭证
输入网络凭证: 用户名是 cat /etc/samba/smb.conf,查看 valid users mxw 为用户名。而不是其他账号名或者用户名,更不是登录计算机时的计算机名; 密码是 需要记住安装samba服务器时,自己设置的password࿱…...
图像处理_积分图
目录 1. 积分图算法介绍 2. 基本原理 2.1 构建积分图 2.2 使用积分图 3. 举个例子 1. 积分图算法介绍 积分图算法是图像处理中的经典算法之一,由Crow在1984年首次提出,它是为了在多尺度透视投影中提高渲染速度。 积分图算法是一种快速计算图像区域和…...
B/S架构SaaS模式 医院云HIS系统源码,自主研发,支持电子病历4级
B/S架构SaaS模式 医院云HIS系统源码,自主研发,支持电子病历4级 系统概述: 一款满足基层医院各类业务需要的云HIS系统。该系统能帮助基层医院完成日常各类业务,提供病患挂号支持、病患问诊、电子病历、开药发药、会员管理、统计查…...
(C)1005 继续(3n+1)猜想
1005 继续(3n1)猜想: 问题描述 卡拉兹(Callatz)猜想已经在1001中给出了描述。在这个题目里,情况稍微有些复杂。 当我们验证卡拉兹猜想的时候,为了避免重复计算,可以记录下递推过程中遇到的每一个数。例如对 n3 进行验证的时候&a…...
编译好的C++应用程序拷贝到其它电脑,提示dll未找到依赖项的解决方法。
编译好的C应用程序拷贝到其它电脑上,运行时出现提示dll未找到依赖项。 由于dll依赖于其它dll,在开发用电脑上的环境不能完全与其它电脑相同。 解决办法是找到调用到的dll依赖的所有dll,拷贝到运行目录下。 在开发电脑上: 1、开…...
wps 开发插件
官方文档参考wps官方文档参考 1.环境安装 安装wps https://www.wps.cn/ 安装Node.js https://nodejs.org/en 安装代码编辑器 Visual Studio Code https://code.visualstudio.com/ 环境检查-进入cmd查看 node -v2.demo 2.1 demo下载 打开vscode,新建终端 安装…...
C语言----数据在内存中的存储
文章目录 前言1.整数在内存中的存储2.大小端字节序和字节序判断2.1 什么是大小端?2.2 练习 3.浮点数在内存中的存储3.1.引子3.2.浮点数的存储3.2.2 浮点数取的过程 前言 下面给大家介绍一下数据在内存中的存储,这个是一个了解c语言内部的知识点…...
【Linux学习】Linux 的虚拟化和容器化技术
˃͈꒵˂͈꒱ write in front ꒰˃͈꒵˂͈꒱ ʕ̯•͡˔•̯᷅ʔ大家好,我是xiaoxie.希望你看完之后,有不足之处请多多谅解,让我们一起共同进步૮₍❀ᴗ͈ . ᴗ͈ აxiaoxieʕ̯•͡˔•̯᷅ʔ—CSDN博客 本文由xiaoxieʕ̯•͡˔•̯᷅ʔ 原创 CSDN 如…...
Delphi 是一种内存安全的语言吗?
上个月,美国政府发布了 "回到基石 "报告: 通往安全和可衡量软件之路 "的报告。该报告是美国网络安全战略的一部分,重点关注多个领域,包括内存安全漏洞和质量指标。 许多在线杂志都对这份报告进行了评论࿰…...
golang语言系列:Scrum、Kanban等敏捷管理策略
云原生学习路线导航页(持续更新中) 本文是 golang语言系列 文章,主要对编程通用技能 Scrum、Kanban等敏捷管理策略 进行学习 1.什么是敏捷开发 敏捷是一个描述软件开发方法的术语,它强调增量交付、团队协作、持续规划和持续学习。…...
QT背景介绍
🐌博主主页:🐌倔强的大蜗牛🐌 📚专栏分类:QT❤️感谢大家点赞👍收藏⭐评论✍️ 目录 一、QT背景 1.1什么是QT 1.2QT的发展历史 1.3什么是框架、库 1.4QT支持的平台 1.5QT的优点 1.6QT的…...
动态规划详解(Dynamic Programming)
目录 引入什么是动态规划?动态规划的特点解题办法解题套路框架举例说明斐波那契数列题目描述解题思路方式一:暴力求解思考 方式二:带备忘录的递归解法方式三:动态规划 推荐练手题目 引入 动态规划问题(Dynamic Progra…...
前端大额计算,真正解决js精度丢失问题
1.解决前端大额计算导致精度丢失问题 2.从底层上解决这个问题,计算时不使用js 运行时计算。 使用rust语言来解决这个问题,因为是底层语言,不涉及到精度问题。 3.实现步骤 步骤 1: 安装工具 确保你已经安装了Rust工具链和wasm-pack&#x…...
Android笔记--MediaCodec(一)
这一节主要来了解一下MediaCodec,Android MediaCodec 是 Android 平台提供的一个用于处理音频和视频数据的 API。它允许开发者对音频和视频数据进行编码和解码,支持多种格式和编解码器。MediaCodec API 通常用于实现实时音视频处理,如视频录制…...
应用升级/灾备测试时使用guarantee 闪回点迅速回退
1.场景 应用要升级,当升级失败时,数据库回退到升级前. 要测试系统,测试完成后,数据库要回退到测试前。 相对于RMAN恢复需要很长时间, 数据库闪回只需要几分钟。 2.技术实现 数据库设置 2个db_recovery参数 创建guarantee闪回点,不需要开启数据库闪回。…...
进程地址空间(比特课总结)
一、进程地址空间 1. 环境变量 1 )⽤户级环境变量与系统级环境变量 全局属性:环境变量具有全局属性,会被⼦进程继承。例如当bash启动⼦进程时,环 境变量会⾃动传递给⼦进程。 本地变量限制:本地变量只在当前进程(ba…...
Spring Boot 实现流式响应(兼容 2.7.x)
在实际开发中,我们可能会遇到一些流式数据处理的场景,比如接收来自上游接口的 Server-Sent Events(SSE) 或 流式 JSON 内容,并将其原样中转给前端页面或客户端。这种情况下,传统的 RestTemplate 缓存机制会…...
连锁超市冷库节能解决方案:如何实现超市降本增效
在连锁超市冷库运营中,高能耗、设备损耗快、人工管理低效等问题长期困扰企业。御控冷库节能解决方案通过智能控制化霜、按需化霜、实时监控、故障诊断、自动预警、远程控制开关六大核心技术,实现年省电费15%-60%,且不改动原有装备、安装快捷、…...
第25节 Node.js 断言测试
Node.js的assert模块主要用于编写程序的单元测试时使用,通过断言可以提早发现和排查出错误。 稳定性: 5 - 锁定 这个模块可用于应用的单元测试,通过 require(assert) 可以使用这个模块。 assert.fail(actual, expected, message, operator) 使用参数…...
【JavaSE】绘图与事件入门学习笔记
-Java绘图坐标体系 坐标体系-介绍 坐标原点位于左上角,以像素为单位。 在Java坐标系中,第一个是x坐标,表示当前位置为水平方向,距离坐标原点x个像素;第二个是y坐标,表示当前位置为垂直方向,距离坐标原点y个像素。 坐标体系-像素 …...
蓝桥杯3498 01串的熵
问题描述 对于一个长度为 23333333的 01 串, 如果其信息熵为 11625907.5798, 且 0 出现次数比 1 少, 那么这个 01 串中 0 出现了多少次? #include<iostream> #include<cmath> using namespace std;int n 23333333;int main() {//枚举 0 出现的次数//因…...
什么是Ansible Jinja2
理解 Ansible Jinja2 模板 Ansible 是一款功能强大的开源自动化工具,可让您无缝地管理和配置系统。Ansible 的一大亮点是它使用 Jinja2 模板,允许您根据变量数据动态生成文件、配置设置和脚本。本文将向您介绍 Ansible 中的 Jinja2 模板,并通…...
【笔记】WSL 中 Rust 安装与测试完整记录
#工作记录 WSL 中 Rust 安装与测试完整记录 1. 运行环境 系统:Ubuntu 24.04 LTS (WSL2)架构:x86_64 (GNU/Linux)Rust 版本:rustc 1.87.0 (2025-05-09)Cargo 版本:cargo 1.87.0 (2025-05-06) 2. 安装 Rust 2.1 使用 Rust 官方安…...
vulnyx Blogger writeup
信息收集 arp-scan nmap 获取userFlag 上web看看 一个默认的页面,gobuster扫一下目录 可以看到扫出的目录中得到了一个有价值的目录/wordpress,说明目标所使用的cms是wordpress,访问http://192.168.43.213/wordpress/然后查看源码能看到 这…...
