当前位置: 首页 > news >正文

蓝桥杯 - 小明的背包1(01背包)

解题思路:

本题属于01背包问题,使用动态规划

dp[ j ]表示容量为 j 的背包的最大价值

注意:

        需要时刻提醒自己dp[ j ]代表的含义,不然容易晕头转向

        注意越界问题,且 j 需要倒序遍历

如果正序遍历

dp[1] = dp[1 - volume[0]] + value[0] = 15

dp[2] = dp[2 - volume[0]] + value[0] = 30

此时dp[2]就已经是30了,意味着物品0,被放入了两次,所以不能正序遍历。

为什么倒叙遍历,就可以保证物品只放入一次呢?

倒叙就是先算dp[2]

dp[2] = dp[2 - volume[0]] + value[0] = 15 (dp数组已经都初始化为0)

dp[1] = dp[1 - volume[0]] + value[0] = 15

所以从后往前循环,每次取得状态不会和之前取得状态重合,这样每种物品就只取一次了。

import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner scan = new Scanner(System.in);int N = scan.nextInt();int V = scan.nextInt();int[] volume = new int[N];int[] value = new int[N];for (int i = 0; i < N; i++) {volume[i] = scan.nextInt();value[i] = scan.nextInt();}int[] dp = new int[V + 1];for (int i = 0; i < N; i++) {//注意越界问题,且 j 需要从大到小遍历for (int j = V; j >= volume[i]; j--) {dp[j] = Math.max(dp[j], dp[j - volume[i]] + value[i]);}}System.out.println(dp[V]);}
}

相关文章:

蓝桥杯 - 小明的背包1(01背包)

解题思路&#xff1a; 本题属于01背包问题&#xff0c;使用动态规划 dp[ j ]表示容量为 j 的背包的最大价值 注意&#xff1a; 需要时刻提醒自己dp[ j ]代表的含义&#xff0c;不然容易晕头转向 注意越界问题&#xff0c;且 j 需要倒序遍历 如果正序遍历 dp[1] dp[1 - vo…...

学习java第二十六天

Spring是一个开源框架&#xff0c;Spring是一个轻量级的Java 开发框架。它是为了解决企业应用开发的复杂性而创建的。框架的主要优势之一就是其分层架构&#xff0c;分层架构允许使用者选择使用哪一个组件&#xff0c;同时为 J2EE 应用程序开发提供集成的框架。Spring使用基本的…...

Go第三方框架--gin框架(二)

4. gin框架源码–Engine引擎和压缩前缀树的建立 讲了这么多 到标题4才开始介绍源码&#xff0c;主要原因还是想先在头脑中构建起 一个大体的框架 然后再填肉 这样不容易得脑血栓。标题四主要涉及标题2.3的步骤一 也就是 标题2.3中的 粗线框中的内容 4.1 Engine 引擎的建立 见…...

五分钟搞懂UDS刷写34/36/37服务(内含S19文件解读)

目录 34服务 36服务 37服务 S19文件介绍 理论太多总是让人头昏&#xff0c;通过举例的方法学习刷写是最好的办法&#xff0c;刷写中最重要的就是34/36/37服务之间的联动&#xff0c;在我当前的项目中37服务较为简单&#xff0c;等待36服务全部传输完成之后&#xff0c;发送…...

知识图谱智能问答系统技术实现

知识图谱是以一种结构化的方式存储和描述知识的数据集合&#xff0c;它将知识表示为节点和边的形式&#xff0c;并可以对这些节点和边进行有意义的存储、查询、连接和关系挖掘等操作。知识图谱不仅可以为人提供理解信息的能力&#xff0c;而且还能为机器提供对信息进行分析、推…...

【unity】如何汉化unity编译器

在【unity】如何汉化unity Hub这篇文章中&#xff0c;我们已经完成了unity Hub的汉化&#xff0c;现在让我们对unity Hub安装的编译器也进行下汉化处理。 第一步&#xff1a;在unity Hub软件左侧栏目中点击安装&#xff0c;选择需要汉化的编译器&#xff0c;再点击设置图片按钮…...

为什么Python不适合写游戏?

知乎上有热门个问题&#xff1a;Python 能写游戏吗&#xff1f;有没有什么开源项目&#xff1f; Python可以开发游戏&#xff0c;但不是好的选择 Python作为脚本语言&#xff0c;一般很少用来开发游戏&#xff0c;但也有不少大型游戏有Python的身影&#xff0c;比如&#xff1…...

查询优化-提升子查询-UNION类型

瀚高数据库 目录 文档用途 详细信息 文档用途 剖析UNION类型子查询提升的条件和过程 详细信息 注&#xff1a;图片较大&#xff0c;可在浏览器新标签页打开。 SQL: SELECT * FROM score sc, LATERAL(SELECT * FROM student WHERE sno 1 UNION ALL SELECT * FROM student…...

【数据结构 | 图论】如何用链式前向星存图(保姆级教程,详细图解+完整代码)

一、概述 链式前向星是一种用于存储图的数据结构&#xff0c;特别适合于存储稀疏图&#xff0c;它可以有效地存储图的边和节点信息&#xff0c;以及边的权重。 它的主要思想是将每个节点的所有出边存储在一起&#xff0c;通过数组的方式连接&#xff08;类似静态数组实现链表…...

气象预测新篇章:Python人工智能的变革力量

Python是功能强大、免费、开源&#xff0c;实现面向对象的编程语言&#xff0c;在数据处理、科学计算、数学建模、数据挖掘和数据可视化方面具备优异的性能&#xff0c;这些优势使得Python在气象、海洋、地理、气候、水文和生态等地学领域的科研和工程项目中得到广泛应用。可以…...

基于微信小程序的民宿短租系统设计与实现(论文+源码)_kaic

摘 要 随着社会的发展&#xff0c;出差、旅游成为常态&#xff0c;也就造成民宿短租市场的兴起。人们新到陌生的环境里找民宿一般都是通过中介。中介虽然可以快速找到合适的民宿但会收取大量的中介费用&#xff0c;这对刚到新环境里的人们来说是一笔大的资金支出。也有一些人通…...

vue3开发前端表单缓存自定义指令,移动端h5必备插件

开发背景 公司需要开发一款移动端应用&#xff0c;使用vue开发&#xff0c;用户录入表单需要本地缓存&#xff0c;刷新页面&#xff0c;或者不小心关掉重新进来&#xff0c;上次录入的信息还要存在。 这里有两种方案&#xff0c;第一种就是像博客平台一样&#xff0c;实时保存…...

骗子查询系统源码

源码简介 小权云黑管理系统 V1.0 功能如下&#xff1a; 1.添加骗子&#xff0c;查询骗子 2.可添加团队后台方便审核用 3.在线反馈留言系统 4.前台提交骗子&#xff0c;后台需要审核才能过 5.后台使用光年UI界面 6.新增导航列表&#xff0c;可给网站添加导航友链 7.可添加云黑类…...

目标检测+车道线识别+追踪

一种方法&#xff1a; 车道线检测-canny边缘检测-霍夫变换 一、什么是霍夫变换 霍夫变换&#xff08;Hough Transform&#xff09;是一种在图像处理和计算机视觉中广泛使用的特征检测技术&#xff0c;主要用于识别图像中的几何形状&#xff0c;尤其是直线、圆和椭圆等常见形状…...

非wpf应用程序项目【类库、用户控件库】中使用HandyControl

文章速览 前言参考文章实现方法1、添加HandyControl包&#xff1b;2、添加资源字典3、修改资源字典内容 坚持记录实属不易&#xff0c;希望友善多金的码友能够随手点一个赞。 共同创建氛围更加良好的开发者社区&#xff01; 谢谢~ 前言 wpf应用程序中&#xff0c;在入口项目中…...

【python】flask执行上下文context,请求上下文和应用上下文原理解析

✨✨ 欢迎大家来到景天科技苑✨✨ &#x1f388;&#x1f388; 养成好习惯&#xff0c;先赞后看哦~&#x1f388;&#x1f388; &#x1f3c6; 作者简介&#xff1a;景天科技苑 &#x1f3c6;《头衔》&#xff1a;大厂架构师&#xff0c;华为云开发者社区专家博主&#xff0c;…...

DDos系列攻击原理与防御原理

七层防御体系 静态过滤 命中黑名单 对确定是攻击的流量直接加入黑名单&#xff08;源地址命中黑名单直接丢弃&#xff0c;缺乏机动性和扩展性&#xff09; 畸形报文过滤 畸形报文攻击 TCP包含多个标记位&#xff0c;排列组合有规律 • 现象&#xff1a;TCP标记位全为1 …...

Python拆分PDF、Python合并PDF

WPS能拆分合并&#xff0c;但却是要输入编辑密码&#xff0c;我没有。故写了个脚本来做拆分&#xff0c;顺便附上合并的代码。 代码如下&#xff08;extract.py) #!/usr/bin/env python """PDF拆分脚本(需要Python3.10)Usage::$ python extract.py <pdf-fil…...

SqlServer(4)经典总结大全-技巧总结-数据开发-基本函数-常识整理-经典面试题

六、技巧 1、11&#xff0c;12的使用&#xff0c;在SQL语句组合时用的较多 “where 11” 是表示选择全部 “where 12”全部不选&#xff0c; 如&#xff1a; if strWhere !‘’ begin set strSQL ‘select count(*) as Total from [’ tblName ] where ’ strWhere …...

ArcGIS矢量裁剪矢量

一、利用相交工具 Arctoolbox工具一分析工具一叠加分析一相交...

第19节 Node.js Express 框架

Express 是一个为Node.js设计的web开发框架&#xff0c;它基于nodejs平台。 Express 简介 Express是一个简洁而灵活的node.js Web应用框架, 提供了一系列强大特性帮助你创建各种Web应用&#xff0c;和丰富的HTTP工具。 使用Express可以快速地搭建一个完整功能的网站。 Expre…...

Golang 面试经典题:map 的 key 可以是什么类型?哪些不可以?

Golang 面试经典题&#xff1a;map 的 key 可以是什么类型&#xff1f;哪些不可以&#xff1f; 在 Golang 的面试中&#xff0c;map 类型的使用是一个常见的考点&#xff0c;其中对 key 类型的合法性 是一道常被提及的基础却很容易被忽视的问题。本文将带你深入理解 Golang 中…...

Spring Boot 实现流式响应(兼容 2.7.x)

在实际开发中&#xff0c;我们可能会遇到一些流式数据处理的场景&#xff0c;比如接收来自上游接口的 Server-Sent Events&#xff08;SSE&#xff09; 或 流式 JSON 内容&#xff0c;并将其原样中转给前端页面或客户端。这种情况下&#xff0c;传统的 RestTemplate 缓存机制会…...

java调用dll出现unsatisfiedLinkError以及JNA和JNI的区别

UnsatisfiedLinkError 在对接硬件设备中&#xff0c;我们会遇到使用 java 调用 dll文件 的情况&#xff0c;此时大概率出现UnsatisfiedLinkError链接错误&#xff0c;原因可能有如下几种 类名错误包名错误方法名参数错误使用 JNI 协议调用&#xff0c;结果 dll 未实现 JNI 协…...

MMaDA: Multimodal Large Diffusion Language Models

CODE &#xff1a; https://github.com/Gen-Verse/MMaDA Abstract 我们介绍了一种新型的多模态扩散基础模型MMaDA&#xff0c;它被设计用于在文本推理、多模态理解和文本到图像生成等不同领域实现卓越的性能。该方法的特点是三个关键创新:(i) MMaDA采用统一的扩散架构&#xf…...

el-switch文字内置

el-switch文字内置 效果 vue <div style"color:#ffffff;font-size:14px;float:left;margin-bottom:5px;margin-right:5px;">自动加载</div> <el-switch v-model"value" active-color"#3E99FB" inactive-color"#DCDFE6"…...

页面渲染流程与性能优化

页面渲染流程与性能优化详解&#xff08;完整版&#xff09; 一、现代浏览器渲染流程&#xff08;详细说明&#xff09; 1. 构建DOM树 浏览器接收到HTML文档后&#xff0c;会逐步解析并构建DOM&#xff08;Document Object Model&#xff09;树。具体过程如下&#xff1a; (…...

学习STC51单片机31(芯片为STC89C52RCRC)OLED显示屏1

每日一言 生活的美好&#xff0c;总是藏在那些你咬牙坚持的日子里。 硬件&#xff1a;OLED 以后要用到OLED的时候找到这个文件 OLED的设备地址 SSD1306"SSD" 是品牌缩写&#xff0c;"1306" 是产品编号。 驱动 OLED 屏幕的 IIC 总线数据传输格式 示意图 …...

【服务器压力测试】本地PC电脑作为服务器运行时出现卡顿和资源紧张(Windows/Linux)

要让本地PC电脑作为服务器运行时出现卡顿和资源紧张的情况&#xff0c;可以通过以下几种方式模拟或触发&#xff1a; 1. 增加CPU负载 运行大量计算密集型任务&#xff0c;例如&#xff1a; 使用多线程循环执行复杂计算&#xff08;如数学运算、加密解密等&#xff09;。运行图…...

k8s业务程序联调工具-KtConnect

概述 原理 工具作用是建立了一个从本地到集群的单向VPN&#xff0c;根据VPN原理&#xff0c;打通两个内网必然需要借助一个公共中继节点&#xff0c;ktconnect工具巧妙的利用k8s原生的portforward能力&#xff0c;简化了建立连接的过程&#xff0c;apiserver间接起到了中继节…...