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

【洛谷贪心算法题】P2240部分背包问题

news 来源：原创 2025/9/13 11:51:16

在这里插入图片描述

【解题思路】

贪心策略选择
- 对于部分背包问题，关键在于如何选择物品放入背包以达到最大价值。由于物品可以分割，遍历排序后的物品数组，根据物品重量和背包剩余容量的关系，决定是将整个物品放入背包还是分割物品放入背包，并更新总价值。。
- 单位重量价值高的物品，在相同重量下能带来更高的价值。所以，我们优先选择单位重量价值高的物品放入背包。
具体实现步骤
- 首先，读入物品的数量、背包容量以及每个物品的重量和价值（结构体存储）。
- 然后，计算每个物品的单位重量价值，并将物品按照单位重量价值从大到小进行排序（自定义排序）。
- 接着，遍历排序后的物品列表，依次将物品放入背包。如果当前物品的重量小于等于背包剩余容量，就将整个物品放入背包，更新背包剩余容量和总价值。
- 如果当前物品的重量大于背包剩余容量，说明不能将整个物品放入背包，此时将物品分割，放入背包剩余容量的部分，计算这部分物品的价值并更新总价值，同时结束循环，因为此时背包已满。

【代码示例】

#include <iostream>
#include <vector>
#include <algorithm>
#include <iomanip> 
using namespace std;// 定义物品结构体，包含重量，价值和单位重量价值
struct Item {double weight;double value;double unitValue;
}; // 自定义比较函数，用于按单位重量价值从大到小排序
bool compare(const Item& a, const Item& b) {return a.unitValue > b.unitValue;
} int main() {int n;double m;cin >> n >> m;vector<Item> items(n);for (int i = 0; i < n; i++) {cin >> items[i].weight >> items[i].value;items[i].unitValue = items[i].value / items[i].weight;}// 按单位重量价值排序sort(items.begin(), items.end(), compare);double totalValue = 0;for (int i = 0; i < n; i++) {if (items[i].weight <= m) {m -= items[i].weight;totalValue += items[i].value;} else {// 正确的做法是累加当前物品按比例放入背包后的价值totalValue += items[i].unitValue * m; m=0;}}// 输出结果，保留三位小数cout << fixed << setprecision(2) << totalValue << endl;return 0;
}

注意：

#include <iomanip> 头文件：使用标准库中与输入输出格式控制相关的功能，具体在代码里用于精确控制输出结果的小数位数。

【洛谷贪心算法题】P2240部分背包问题

【解题思路】贪心策略选择对于部分背包问题，关键在于如何选择物品放入背包以达到最大价值。由于物品可以分割，遍历排序后的物品数组，根据物品重量和背包剩余容量的关系，决定是将整个物品放入背包还是分割物品放入背包&#xff…...

编程日记 2025/9/13 11:51:16

ArcGIS Pro技巧实战：高效矢量化天地图地表覆盖图

在地理信息系统（GIS）领域，地表覆盖图的矢量化是一项至关重要的任务。天地图作为中国国家级的地理信息服务平台，提供了丰富且详尽的地表覆盖数据。然而，这些数据通常以栅格格式存在，不利于进行空间分析和数据…...

编程日记 2025/9/8 17:25:13

AF3 pair_sequences函数解读

AlphaFold3 msa_pairing模块的pair_sequences函数的核心目标是基于 MSA（多序列比对）中的物种信息，在多条链之间建立 MSA 配对索引，从而帮助 AlphaFold3 捕捉共进化信息，提升蛋白复合物预测的准确性。函数pair_sequences 通过调用 _make_msa_df、 _create_species_dict 以…...

编程日记 2025/9/13 11:48:54

在VSCode 中使用通义灵码最新版详细教程

在 VSCode 中使用通义灵码：最新版详细教程与使用场景 Visual Studio Code（简称 VSCode）是一款由微软开发的轻量级、功能强大的开源代码编辑器，支持多种编程语言，深受开发者喜爱。而通义灵码（TONGYI Lingma…...

编程日记 2025/9/9 3:53:20

ssh和rdp踩坑

ssh和rdp（远程桌面）踩坑使用微软账号登录windows的话，ssh的用户名是本地用户名（就是c盘用户文件夹下的用户名），rdp的用户名是微软账号用户名，但是密码都是微软账号的密码，跟登录密…...

编程日记 2025/9/10 18:10:07

Linux驱动学习(四)--字符设备注册

上一节讲到的字符设备注册与销毁是通过cdev_init、cdev_add、cdev_del等函数分步执行的，本小节用一种更简单的方式，来注册字符设备 register_chrdev 如果major为0，该函数将动态的分配一个主设备号并且返回对应的值如果major > 0&#xff…...

编程日记 2025/9/8 16:58:18

vue3 下载文件 responseType-blob 或者 a标签

在 Vue 3 中，你可以使用 axios 或 fetch 来下载文件，并将 responseType 设置为 blob 以处理二进制数据。以下是一个使用 axios 的示例： 使用 axios 下载文件首先，确保你已经安装了 axios： npm install axios然后在你…...

编程日记 2025/9/13 11:51:13

Meta最新研究：从单张照片到3D数字人的革命性突破

随着人工智能技术的发展，3D建模和虚拟人物生成逐渐变得更加普及和高效。Meta（前身为Facebook）的最新研究成果展示了如何仅通过一张普通手机拍摄的照片就能生成高质量、全方位的3D数字人。这项技术不仅适用于虚拟试衣、游戏角色建模，还能广泛应用于AR/VR内容生成等领域。本文…...

编程日记 2025/9/11 6:34:58

大中型虚拟化园区网络设计

《大中型虚拟化园区网络设计》属于博主的“园区网”专栏，若想成为HCIE，对于园区网相关的知识需要非常了解，更多关于园区网的内容博主会更新在“园区网”专栏里，请持续关注！ 一.前言华为云园区网络解决方案(简称Cloud…...

编程日记 2025/9/13 3:23:14

Vue 项目中配置代理的必要性与实现指南

Vue 项目中配置代理的必要性与实现指南在 Vue 前端项目的开发过程中，前端与后端地址通常不同，可能引发跨域问题。为了在开发环境下顺畅地请求后端接口，常常会通过配置**代理（proxy）**来解决问题。这篇文章将详细解析…...

编程日记 2025/9/10 11:44:42

目录完整代码代码解释完整代码 import chromadb chroma_client chromadb.Client()collection chroma_client.create_collection(name"my_collection")collection.add(documents["This is a document about pineapple","This is a document about…...

编程日记 2025/9/9 16:18:13

玩机日记 12 fnOS使用lucky反代https转发到外网提供服务

目录 1、安装lucky 2、更新lucky 3、上传ssl证书 4、设置安全入口，替换fnOS的应用url 5、添加https反代这一篇主要是解决一下飞牛反代https的问题。可以先看玩机日记 12.5 在PVE Windows11上部署本地AI模型，使用群晖反代https转发到外网提供服务&a…...

编程日记 2025/9/12 23:36:28

5分钟学会SpringAI

引言要开发一个Spring AI的入门案例，我们可以从一个简单的Spring Boot项目开始，然后集成Spring AI的功能来实现基本的生成式AI任务。下面是一个步骤指南，帮助你快速启动并运行一个简单的Spring AI应用。步骤 1: 准备环境首先&#xff0…...

编程日记 2025/9/8 12:49:23

专业的UML开发工具StarUML

专业的UML开发工具StarUML 可靠的软件建模软件StarUML StarUML 是一款支持统一建模语言 (UML)框架的开源建模软件。它提供了几种类型的图表，并允许用户生成多种语言的代码。在它的帮助下，软件开发人员可以创建设计、概念和编码解决方案。但是&#xff0…...

编程日记 2025/9/9 1:49:26

go语言环境下载与配置（Windows）

下载 Go下载 - Go语言中文网 - Golang中文社区建议在D盘中创建文件夹安装到 D 盘 ，方便进行管理，然后进行傻瓜式安装。安装验证安装 go version 安装成功配置环境变量 winE --> 右击此电脑 --> 选择属性 --> 高级系统设置 --> 点击…...

编程日记 2025/9/9 22:54:35

矩阵系列题解

1.洛谷 P1962 斐波那契数列题意大家都知道，斐波那契数列是满足如下性质的一个数列： F n { 1 ( n ≤ 2 ) F n − 1 F n − 2 ( n ≥ 3 ) F_n \left\{\begin{aligned} 1 \space (n \le 2) \\ F_{n-1}F_{n-2} \space (n\ge 3) \end{aligned}\right. …...

编程日记 2025/9/9 10:27:29

C++ 正则表达式分组捕获入门指南

在 C 中，正则表达式（regex）是一种用于匹配字符串模式的强大工具。正则表达式不仅能帮助你查找符合特定模式的字符，还能捕获匹配的子字符串（即分组捕获）。这篇文章将介绍 C 正则表达式中的分组捕获机制&…...

编程日记 2025/9/9 4:24:09

动态数据表格：基于 PrimeFaces 的运行时列选择实现

在现代的 Web 应用开发中，动态数据表格是一个非常实用的功能，它允许用户根据自己的需求选择显示哪些列。这种灵活性不仅提升了用户体验，还能适应不同的数据展示需求。今天，我们将通过一个具体的实现案例，展示如何使用 …...

编程日记 2025/9/10 19:55:24

Plugin ‘mysql_native_password‘ is not loaded`

Plugin ‘mysql_native_password’ is not loaded mysql_native_password介绍1. 使用默认的认证插件2. 修改 my.cnf 或 my.ini 配置文件3. 加载插件（如果确实没有加载）4. 重新安装或检查 MySQL 版本遇到错误 ERROR 1524 (HY000): Plugin mysql_nativ…...

编程日记 2025/9/9 12:01:31

Kotlin 知识点二延迟初始化和密封类

对变量延迟初始化 Kotlin 语言的许多特性，包括变量不可变，变量不可为空，等等。这些特性都是为了尽可能地保证程序安全而设计的，但是有些时候这些特性也会在编码时给我们带来不少的麻烦。比如，如果你的类中存在很多…...

编程日记 2025/9/8 5:04:03

DeepSeek开源周第二弹：DeepEP如何用RDMA+FP8让MoE模型飞起来？

一、引言：MoE模型的通信瓶颈与DeepEP的诞生在混合专家（MoE）模型训练中，专家间的全对全（All-to-All）通信成为性能瓶颈。传统方案在跨节点传输时带宽利用率不足50%，延迟高达300μs以上。DeepSee…...

编程日记 2025/9/13 11:48:54

C++ Primer 成员访问运算符

欢迎阅读我的【CPrimer】专栏专栏简介：本专栏主要面向C初学者，解释C的一些基本概念和基础语言特性，涉及C标准库的用法，面向对象特性，泛型特性高级用法。通过使用标准库中定义的抽象设施，使你更加适应高级…...

编程日记 2025/9/2 7:35:02

无人机遥控器的亮度和两个工作频率

工作频率 2.4000-2.4835 GHz ， 5.725-5.850 GHz 1.这是一个无人机的遥控器的两个工作频率，为什么会有两个工作频率？ 无人机的遥控器采用双频段设计（2.4GHz 和 5.8GHz），主要是为了解决以下问题并优化性…...

编程日记 2025/9/13 11:51:15

ubuntu20.04安装docker

3台主机，2台都能正确安装，第三台怎么都安装不成功； 3台主机都是一样的配置和系统； 后来看来是其外网的ip不一样，导致第三台主机可能被Qiang，不过错误只是提示签名不正确，在设置签名时好像没有…...

编程日记 2025/9/8 4:04:08

【含文档+PPT+源码】基于过滤协同算法的旅游推荐管理系统设计与实现

项目介绍本课程演示的是一款基于过滤协同算法的旅游推荐管理系统设计与实现，主要针对计算机相关专业的正在做毕设的学生与需要项目实战练习的 Java 学习者。 1.包含：项目源码、项目文档、数据库脚本、软件工具等所有资料 2.带你从零开始部署运行本套系…...

编程日记 2025/9/12 8:45:21

深入解析Crawl4AI：为AI应用量身定制的高效开源爬虫框架

引言在当今数据驱动的时代，人工智能（AI）和大型语言模型（LLM）的发展对高质量数据的需求日益增长。如何高效地从互联网上获取、处理和提取有价值的数据，成为了研究人员和开发者面临的关键挑战。Crawl4AI作为…...

编程日记 2025/9/11 17:30:55

《Effective Objective-C》阅读笔记（下）

目录内存管理理解引用计数引用计数工作原理自动释放池保留环以ARC简化引用计数使用ARC时必须遵循的方法命名规则变量的内存管理语义 ARC如何清理实例变量在dealloc方法中只释放引用并解除监听编写“异常安全代码”时留意内存管理问题以弱引用避免保留环 …...

编程日记 2025/9/12 18:50:25

深度生成模型（二）——基本概念与数学建模

上一篇笔记中提到了端到端模型底层核心采用了深度生成模型，先简单梳理一下生成式人工智能（Artificial Intelligence Generated Content，AIGC）经历了从早期基于概率模型和规则系统的方法到现代深度生成模型的跨越式发展深度神经…...

编程日记 2025/9/8 0:57:21

4.WebSocket 配置与Nginx 的完美结合

序言在现代 web 应用中，WebSocket 作为一种全双工通信协议，为实时数据传输提供了强大的支持。若要确保 WebSocket 在生产环境中的稳定性和性能，使用 Nginx 作为反向代理服务器是一个明智的选择。本篇文章将带你了解如何在 Nginx 中配置 Web…...

编程日记 2025/9/13 11:51:15

【R语言】dplyr包经典函数summarise函数

dplyr包经典函数summarise函数，后面改名乘reframe函数了，但是summarise仍然适用这个函数的返回结果是一个新的数据框，下面讲一下几种常见用法示例数据为R自带的数据集mtcars 1.不分组 mtcars %>%summarise(mean mean(disp), n n()…...

编程日记 2025/9/12 11:04:28

Cuppa CMS v1.0 任意文件读取（CVE-2022-25401）

漏洞简介： Cuppa CMS v1.0 administrator/templates/default/html/windows/right.php文件存在任意文件读取漏洞漏洞环境： 春秋云镜中的漏洞靶标，CVE编号为CVE-2022-25401 漏洞复现弱口令行不通直接访问administrator/templates/defau…...

编程日记 2025/9/8 0:43:17

8.Dashboard的导入导出

分享自己的Dashboard 1. 在Dashboard settings中选择 JSON Model 2. 导入后续请参考第三篇导入光放Dashboard，相近...

编程日记 2025/9/2 13:25:00

RabbitMQ 的介绍与使用

一. 简介 1> 什么是MQ 消息队列（Message Queue，简称MQ），从字面意思上看，本质是个队列，FIFO先入先出，只不过队列中存放的内容是message而已。其主要用途：不同进程Process/线程T…...

编程日记 2025/9/2 14:24:15

unity学习58：下拉列表框 dropdown的caption和options

目录 1 下拉列表框 dropdown 1.1 创建dropdown 1.2 dropdown的子物体构成 1.3 drop的子物体构成:默认灰色的模板 template 1.3.1 默认灰色的模板 template 实际是生效的，只是不直接显示 1.3.2 其中 item下面是下拉选项的格式 1.3.3 可以修改和新增 1.4 drop…...

编程日记 2025/9/9 1:49:30

STM32中使用PWM对舵机控制

目录 1、硬件JIE 2、PWM口配置 3、角度转换 4、main函数中应用 5、工程下载连接 1、硬件介绍单片机：STM32F1 舵机：MG995 2、PWM口配置 20毫秒的PWM脉冲占空比，对舵机控制效果较好计算的公式： PSC、ARR值的选取&#xf…...

编程日记 2025/8/23 9:45:13

如何免费使用稳定的deepseek

0、背景： 在AI辅助工作中，除了使用cursor做编程外，使用deepseek R1进行问题分析、数据分析、代码分析效果非常好。现在我经常会去拿行业信息、遇到的问题等去咨询R1，也给了自己不少启示。但是由于官网稳定性很差，很多…...

编程日记 2025/8/17 22:03:36

STM32内存五区及堆栈空间大小设置（启动文件浅析）

前言嘿，朋友们！今天咱们来聊聊STM32的内存五区和堆栈空间大小设置。这可是嵌入式开发里的“必修课”，要是没整明白，程序说不定就“翻车”了。别担心，我这就带你一步步搞懂这事儿，让你轻松上手&#xff0c…...

编程日记 2025/9/9 20:00:29

LVS+Keepalived高可用群集配置案例

以下是一个 LVSKeepalived 高可用群集配置案例： 1、环境准备 LVS 主调度器（lvs1）：IP 地址为 192.168.8.101，心跳 IP 为 192.168.4.101LVS 备调度器（lvs2）：IP 地址为 192.168.8.102…...

编程日记 2025/9/9 10:24:56

MySQL 中如何解决深度分页的问题？ MySQL中 join、inner join、left join、right join区别

MySQL 中如何解决深度分页的问题？ 在 MySQL 中解决深度分页问题的核心思路是减少扫描的数据量，尤其是避免通过 LIMIT offset, size 导致的大范围数据扫描。以下是三种优化方法及其原理、适用场景和注意事项： 1. 子查询覆盖索引&#xff08…...

编程日记 2025/9/9 1:12:11

本地部署DeepSeek-R1（Ollama+Docker+OpenWebUI知识库）

安装Ollama 打开 Ollama官网 https://ollama.com/下载安装 Ollama服务默认只允许本机访问，修改允许其它主机访问 OLLAMA_HOST0.0.0.0 ollama serve也可以添加系统环境变量都知道模型体积很大，顺便也通过环境变量修改模型存放位置，我这…...

编程日记 2025/9/13 1:14:22

ubuntu22.04安装docker engine

在Ubuntu 22.04上安装Docker Engine可以通过以下步骤完成： 更新系统包索引： sudo apt update安装必要的依赖包： 这些包允许apt通过HTTPS使用仓库。 sudo apt install -y apt-transport-https ca-certificates curl software-properties-commo…...

编程日记 2025/9/12 14:27:01

Protobuf原理与序列化

本文目录 1. Protobuf介绍2. Protobuf的优势3. 编写Protobuf头部全局定义消息结构具体定义字段类型定义标签号Base128编码 4. TLVProtobuf的TLV编码如何通过Varint表示300？ 5. 编译Protobuf6. 构造消息对象前言：之前写项目的时候只是简单用了下Protobuf…...

编程日记 2025/9/11 7:28:52

Redis｜事务

文章目录是什么能干嘛Redis 事务 VS 数据库事务怎么玩小总结是什么首先回想一下什么是数据库的事务？数据库事务是指作为单个逻辑单元执行的一系列操作，具备以下四个关键特性（ACID）： 原子性（Atomicity&am…...

编程日记 2025/9/7 20:54:27

树莓百度百科更新！宜宾园区业务再添新篇

树莓集团宜宾园区业务不断拓展，主要体现在以下几个方面： 产业布局 -聚焦数字经济核心领域：涵盖软件开发、人工智能、大数据等，吸引众多上下游企业入驻，形成从芯片研发、软件开发到系统集成的完整产业链条。 -推进“双…...

编程日记 2025/9/8 21:18:22

设计模式教程：模板方法模式（Template Method Pattern）

一、概述模板方法模式（Template Method Pattern） 是一种行为型设计模式，旨在定义一个操作中的算法骨架，而将一些步骤的具体实现延迟到子类中。通过模板方法模式，父类可以不改变算法结构的情况下，让子类重…...

编程日记 2025/9/11 1:00:21

unity学习54：图片+精灵+遮罩mask，旧版文本 text 和新的TMP文本

目录 1 图片 image 1.1 如果直接导入image 1.2 图片 image 和精灵 sprite 1.2.1 继续修改上面的格式 texture type 是default 1.2.2 再次关联到UI的 image 物体上就可以了 1.3 图片和遮罩 mask 1.3.1 创建1个父物体和1个子物体，分别都是image 1.3.2 如果父…...

编程日记 2025/9/9 20:49:22

【Java项目】基于Spring Boot的校园闲置物品交易网站

【Java项目】基于Spring Boot的校园闲置物品交易网站技术简介：采用Java技术、Spring Boot框架、MySQL数据库等实现。系统简介：校园闲置物品交易网站是一个典型的管理系统，主要功能包括管理员：首页、个人中心、用户管理、商品类…...

编程日记 2025/9/10 5:21:19

网页制作08-html,css,javascript初认识のhtml使用框架结构，请先建立站点！

框架一般由框架集和框架组成。框架集就像一个大的容器，包括所有的框架，是框架的集合。框架是框架集中一个独立的区域用于显示一个独立的网页文档。框架集是文件html，它定义一组框架的布局和属性，包括框架的数目，框架…...

编程日记 2025/9/9 4:49:34

DeepSeek-R1：通过强化学习激励大语言模型的推理能力

摘要本文介绍了我们的第一代推理模型，DeepSeek-R1-Zero 和 DeepSeek-R1。DeepSeek-R1-Zero 是通过大规模强化学习（RL）训练的模型，在没有使用监督微调（SFT）这个前置步骤的情况下，展示了卓越的推…...

编程日记 2025/9/13 5:57:05

hbase笔记总结1

hbase是nosql的一种，非关系型数据库，not only sql，可处理大规模、高并发的数据，是web2.0以后的产物hbase的扩展性和灵活性更好，而且筛选能力相较于MySQL更优nosql的四大特点： 灵活的数据模型 （1…...

编程日记 2025/9/9 18:41:29

相关文章：