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

【洛谷 P1616】疯狂的采药 题解(动态规划+完全背包)

疯狂的采药

题目背景

此题为纪念 LiYuxiang 而生。

题目描述

LiYuxiang 是个天资聪颖的孩子,他的梦想是成为世界上最伟大的医师。为此,他想拜附近最有威望的医师为师。医师为了判断他的资质,给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说:“孩子,这个山洞里有一些不同种类的草药,采每一种都需要一些时间,每一种也有它自身的价值。我会给你一段时间,在这段时间里,你可以采到一些草药。如果你是一个聪明的孩子,你应该可以让采到的草药的总价值最大。”

如果你是 LiYuxiang,你能完成这个任务吗?

此题和原题的不同点:

1 1 1. 每种草药可以无限制地疯狂采摘。

2 2 2. 药的种类眼花缭乱,采药时间好长好长啊!师傅等得菊花都谢了!

输入格式

输入第一行有两个整数,分别代表总共能够用来采药的时间 t t t 和代表山洞里的草药的数目 m m m

2 2 2 到第 ( m + 1 ) (m + 1) (m+1) 行,每行两个整数,第 ( i + 1 ) (i + 1) (i+1) 行的整数 a i , b i a_i, b_i ai,bi 分别表示采摘第 i i i 种草药的时间和该草药的价值。

输出格式

输出一行,这一行只包含一个整数,表示在规定的时间内,可以采到的草药的最大总价值。

样例 #1

样例输入 #1

70 3
71 100
69 1
1 2

样例输出 #1

140

提示

数据规模与约定
  • 对于 30 % 30\% 30% 的数据,保证 m ≤ 1 0 3 m \le 10^3 m103
  • 对于 100 % 100\% 100% 的数据,保证 1 ≤ m ≤ 1 0 4 1 \leq m \le 10^4 1m104 1 ≤ t ≤ 1 0 7 1 \leq t \leq 10^7 1t107,且 1 ≤ m × t ≤ 1 0 7 1 \leq m \times t \leq 10^7 1m×t107 1 ≤ a i , b i ≤ 1 0 4 1 \leq a_i, b_i \leq 10^4 1ai,bi104

思路

在这个问题中,有一个背包,其容量是时间t,还有m种不同的草药,每种草药都有自己的采集时间a[i]和价值b[i]。目标是在不超过背包容量的情况下,最大化背包中草药的总价值。

可以将每种草药视为一种物品,其“重量”是采集时间,其“价值”是草药的价值。这个问题的特点是,每种草药可以无限次采集,只要时间允许。这就是所谓的“完全背包”问题。

定义状态dp[j]为当背包容量为j时,能够获得的最大价值。初始化状态时,假设背包为空,所以所有的dp[j]都为0。

然后开始填充状态表。对于每种草药i,都会尝试将其添加到背包中,看看是否能提高背包的总价值。具体来说,对于每个可能的背包容量j,如果可以将草药i添加到背包中(即j >= a[i]),那么就有两种选择:一是不添加草药i,此时背包的总价值仍然是dp[j];二是添加草药i,此时背包的总价值变为dp[j - a[i]] + b[i]。目标是使背包的总价值最大,所以选择两者中的较大值作为新的dp[j]

这是完全背包问题,而不是01背包问题。在完全背包问题中,每种物品可以被选择多次,因此在考虑是否选择当前物品时,需要查看在选择该物品多次的情况下能够获得的最大价值。

在这个问题中,for (int j = a[i]; j <= t; j++) 的作用是遍历所有可能选择当前物品的情况。由于可以选择当前物品多次,因此需要从小到大遍历 j。这样,当考虑到 j 时,dp[j - a[i]] 对应的是已经选择了当前物品的情况,因此 dp[j] 可以通过选择当前物品来更新。

如果从大到小遍历 j,即 for (int j = t; j >= a[i] j--),那么当考虑到 j 时,dp[j - a[i]] 对应的是还没有选择当前物品的情况,因此 dp[j] 只能通过不选择当前物品来更新。这就变成了01背包问题,每种物品只能被选择一次。

最后输出dp[t],这就是当背包容量为t时,能够获得的最大价值,也就是答案。


AC代码

#include <algorithm>
#include <iostream>
#define AUTHOR "HEX9CF"
#define ll long long
using namespace std;const int N = 1e7 + 7;int t, m;
// 时间,价值
int a[N], b[N];
ll dp[N];int main() {cin >> t >> m;for (int i = 1; i <= m; i++) {cin >> a[i] >> b[i];}for (int i = 1; i <= m; i++) {for (int j = a[i]; j <= t; j++) {dp[j] = max(dp[j], dp[j - a[i]] + b[i]);}}cout << dp[t] << endl;return 0;
}

相关文章:

【洛谷 P1616】疯狂的采药 题解(动态规划+完全背包)

疯狂的采药 题目背景 此题为纪念 LiYuxiang 而生。 题目描述 LiYuxiang 是个天资聪颖的孩子&#xff0c;他的梦想是成为世界上最伟大的医师。为此&#xff0c;他想拜附近最有威望的医师为师。医师为了判断他的资质&#xff0c;给他出了一个难题。医师把他带到一个到处都是草…...

L1-027 出租分数 20

下面是新浪微博上曾经很火的一张图&#xff1a; 一时间网上一片求救声&#xff0c;急问这个怎么破。其实这段代码很简单&#xff0c;index数组就是arr数组的下标&#xff0c;index[0]2 对应 arr[2]1&#xff0c;index[1]0 对应 arr[0]8&#xff0c;index[2]3 对应 arr[3]0&…...

51单片机精进之路-1点亮led灯

本例中led灯使用共阳极连接在电路中&#xff0c;共阳极即将led的正极接在一起&#xff0c;通过上拉电阻接到电源正极&#xff0c;通过单片机io与Led的负极相连&#xff0c;io输出低电平&#xff0c;有电流从led流过&#xff0c;此时led点亮&#xff0c;当io输出高电平时&#x…...

嵌入式学习Day14 C语言 --- 位运算

位运算 注意&#xff1a;符号位也遵循这个规则 一、按位与(&) 运算规则&#xff1a;一假则假 int a 0x33;a & 0x55;0011 00110101 0101 &----------0001 0001 //0x11 二、按位或(|) 运算规则&#xff1a;一真则真 int a 0x33;a |0x55;0011 00110101 0101 |…...

idea设置terminal为git

要在IntelliJ IDEA中设置终端为Git Bash&#xff0c;请按照以下步骤操作&#xff1a; 打开 Settings&#xff08;设置&#xff09;。点击 Tools&#xff08;工具&#xff09;选项卡。进入 Terminal&#xff08;终端&#xff09;界面。在 Shell Path 下选择 Browse&#xff08;…...

《MySQL 简易速速上手小册》第3章:性能优化策略(2024 最新版)

文章目录 3.1 查询优化技巧3.1.1 基础知识3.1.2 重点案例3.1.3 拓展案例 3.2 索引和查询性能3.2.1 基础知识3.2.2 重点案例3.2.3 拓展案例 3.3 优化数据库结构和存储引擎3.3.1 基础知识3.3.2 重点案例3.3.3 拓展案例 3.1 查询优化技巧 让我们来聊聊如何让你的 MySQL 查询跑得像…...

【golang】23、gorilla websocket 源码:examples、数据结构、流程

文章目录 一、examples1.1 echo1.1.1 server.go1.1.2 client.go 1.2 command1.2.1 功能和启动方式1.2.2 home.html1.2.3 main.go 1.3 filewatch1.3.1 html1.3.2 serveHome 渲染模板1.3.3 serveWs1.3.4 writer() 1.4 buffer pool1.4.1 server1.4.2 client 1.5 chat1.5.1 server1…...

SpringCloud+RabbitMQ+Docker+Redis+搜索+分布式 基础(持续更新~)

具体操作&#xff1a; day2: 作用&#xff1a; 出现跨域问题 配相对应进行配置即可解决&#xff1a; IDEA连接的&#xff0c;在url最后加参数?useSSLfalse注意链接密码是123&#xff08;docker中mysql密码&#xff09; 注意&#xff0c;虚拟机中设置的密码和ip要和主机上…...

flask+pyinstaller实现mock接口,并打包到exe运行使用postman验证

flask代码 from flask import Flask, request, jsonifyapp Flask(__name__)app.route("/login", methods[POST]) def login():username request.json.get("username").strip() # 用户名password request.json.get("password").strip() # 密…...

【Spring Boot】第一篇 创建简单的Spring Boot项目

导航 一. 简介二. 创建简单的Spring Boot项目1. 工具选择和版本确定2. 创建步骤 三. 部署项目四. 测试验证 一. 简介 Spring Boot是一个用于构建独立的、生产级别的Spring应用程序的框架。它简化了Spring应用程序的创建和配置过程&#xff0c;同时提供了很多开箱即用的功能&am…...

SSL协议是什么?关于SSL和TLS的常见问题解答

SSL&#xff08;安全套接字层&#xff09;及其后继者TLS&#xff08;传输层安全&#xff09;是用于在联网计算机之间建立经过身份验证和加密的链接的协议。尽管SSL协议在 1999年已经随着TLS 1.0的发布而被弃用&#xff0c;但我们仍将这些相关技术称为“SSL”或“SSL/TLS”。那么…...

第十五个知识:JQuery

初识JQuery: <head><meta charset"UTF-8"><title>Title</title><script src"lib/jquery-3.7.1.js"></script>//引入jquery </head> <body><a href"https://www.baidu.com" id"baidu&q…...

用Matlab 2015a svmtrain函数训练的SVM model在2021b无法使用的解决方法

背景 与r2015a版本的Matlab相比&#xff0c;r2021b版本中包含更多集成好的算法模块&#xff08;尤其是深度学习的模块&#xff09;&#xff0c;想把原来r2015a版本的代码升级到r2021b高版本的Matlab已经采用fitcsvm函数和predict函数替代了旧版本中svmtrain函数和svmclassify函…...

umount:/home/tuners/windows files:目标忙。

您提到的错误信息 "umount: /home/tuners/windows files: 目标忙。" 是在尝试卸载&#xff08;umount&#xff09;一个文件系统时常见的错误。这个错误表明有一些进程仍然在使用挂载点&#xff08;/home/tuners/windows files&#xff09;下的文件或目录&#xff0c;…...

FPGA_vga显示

一 VGA 1.1 VGA VGA是视频图像阵列&#xff0c;是一种使用模拟信号进行视频传输的标准协议。 1.2 VGA接引脚定义 VGA分公母两种&#xff0c;RGB显示标准。 1.3 VGA显示器 VGA显示器采用图像扫描的方式进行图像显示&#xff0c;将构成图像的像素点&#xff0c;在行同步信号…...

sklearn模型指标和特征贡献度查看

文章目录 算法介绍r2_scoretrain_test_splitDecisionTreeRegressor参考文献支持快速查看traget和特征之间的关系 # -*- coding: utf-8 -*- import pandas as pd pd.set_option(display.max_columns, None) pd.set_option...

2024.2.6日总结(小程序开发3)

页面配置 页面配置和全局配置的关系&#xff1a; 小程序中&#xff0c;app.json中的window节点&#xff0c;可以全局配置小程序中每个页面的窗口表现 如果某些小程序想要有特殊的窗口表现&#xff0c;可以用页面级别的.json配置文件实现这个需求 页面配置和全局配置冲突时&…...

相机图像质量研究(10)常见问题总结:光学结构对成像的影响--光圈

系列文章目录 相机图像质量研究(1)Camera成像流程介绍 相机图像质量研究(2)ISP专用平台调优介绍 相机图像质量研究(3)图像质量测试介绍 相机图像质量研究(4)常见问题总结&#xff1a;光学结构对成像的影响--焦距 相机图像质量研究(5)常见问题总结&#xff1a;光学结构对成…...

TCP和UDP相关问题(重点)(3)——3.HTTP基于TCP还是UDP?

HTTP/3.0 之前是基于 TCP 协议的&#xff0c;而 HTTP/3.0 将弃用 TCP&#xff0c;改用 基于 UDP 的 QUIC 协议 。具体见HTTP相关问题-CSDN博客...

基于modbus rtu协议操作PLC的EPICS示例

硬件设备 本实验中使用到的设备如下&#xff1a; 1、S7-200 Smart SR20 PLC 作为受控设备&#xff0c;执行机构。 S7-200 Smart是西门子的一款小型PLC产品&#xff08;以下简称Smart系列&#xff09;。 Smart系列PLC是西门子公司经过大量调研&#xff0c;为中国小型自动化…...

IDEA运行Tomcat出现乱码问题解决汇总

最近正值期末周&#xff0c;有很多同学在写期末Java web作业时&#xff0c;运行tomcat出现乱码问题&#xff0c;经过多次解决与研究&#xff0c;我做了如下整理&#xff1a; 原因&#xff1a; IDEA本身编码与tomcat的编码与Windows编码不同导致&#xff0c;Windows 系统控制台…...

装饰模式(Decorator Pattern)重构java邮件发奖系统实战

前言 现在我们有个如下的需求&#xff0c;设计一个邮件发奖的小系统&#xff0c; 需求 1.数据验证 → 2. 敏感信息加密 → 3. 日志记录 → 4. 实际发送邮件 装饰器模式&#xff08;Decorator Pattern&#xff09;允许向一个现有的对象添加新的功能&#xff0c;同时又不改变其…...

2024年赣州旅游投资集团社会招聘笔试真

2024年赣州旅游投资集团社会招聘笔试真 题 ( 满 分 1 0 0 分 时 间 1 2 0 分 钟 ) 一、单选题(每题只有一个正确答案,答错、不答或多答均不得分) 1.纪要的特点不包括()。 A.概括重点 B.指导传达 C. 客观纪实 D.有言必录 【答案】: D 2.1864年,()预言了电磁波的存在,并指出…...

【Go】3、Go语言进阶与依赖管理

前言 本系列文章参考自稀土掘金上的 【字节内部课】公开课&#xff0c;做自我学习总结整理。 Go语言并发编程 Go语言原生支持并发编程&#xff0c;它的核心机制是 Goroutine 协程、Channel 通道&#xff0c;并基于CSP&#xff08;Communicating Sequential Processes&#xff0…...

视频字幕质量评估的大规模细粒度基准

大家读完觉得有帮助记得关注和点赞&#xff01;&#xff01;&#xff01; 摘要 视频字幕在文本到视频生成任务中起着至关重要的作用&#xff0c;因为它们的质量直接影响所生成视频的语义连贯性和视觉保真度。尽管大型视觉-语言模型&#xff08;VLMs&#xff09;在字幕生成方面…...

Robots.txt 文件

什么是robots.txt&#xff1f; robots.txt 是一个位于网站根目录下的文本文件&#xff08;如&#xff1a;https://example.com/robots.txt&#xff09;&#xff0c;它用于指导网络爬虫&#xff08;如搜索引擎的蜘蛛程序&#xff09;如何抓取该网站的内容。这个文件遵循 Robots…...

Spring AI 入门:Java 开发者的生成式 AI 实践之路

一、Spring AI 简介 在人工智能技术快速迭代的今天&#xff0c;Spring AI 作为 Spring 生态系统的新生力量&#xff0c;正在成为 Java 开发者拥抱生成式 AI 的最佳选择。该框架通过模块化设计实现了与主流 AI 服务&#xff08;如 OpenAI、Anthropic&#xff09;的无缝对接&…...

OPenCV CUDA模块图像处理-----对图像执行 均值漂移滤波(Mean Shift Filtering)函数meanShiftFiltering()

操作系统&#xff1a;ubuntu22.04 OpenCV版本&#xff1a;OpenCV4.9 IDE:Visual Studio Code 编程语言&#xff1a;C11 算法描述 在 GPU 上对图像执行 均值漂移滤波&#xff08;Mean Shift Filtering&#xff09;&#xff0c;用于图像分割或平滑处理。 该函数将输入图像中的…...

【笔记】WSL 中 Rust 安装与测试完整记录

#工作记录 WSL 中 Rust 安装与测试完整记录 1. 运行环境 系统&#xff1a;Ubuntu 24.04 LTS (WSL2)架构&#xff1a;x86_64 (GNU/Linux)Rust 版本&#xff1a;rustc 1.87.0 (2025-05-09)Cargo 版本&#xff1a;cargo 1.87.0 (2025-05-06) 2. 安装 Rust 2.1 使用 Rust 官方安…...

虚拟电厂发展三大趋势:市场化、技术主导、车网互联

市场化&#xff1a;从政策驱动到多元盈利 政策全面赋能 2025年4月&#xff0c;国家发改委、能源局发布《关于加快推进虚拟电厂发展的指导意见》&#xff0c;首次明确虚拟电厂为“独立市场主体”&#xff0c;提出硬性目标&#xff1a;2027年全国调节能力≥2000万千瓦&#xff0…...