【洛谷 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 m≤103 。
- 对于 100 % 100\% 100% 的数据,保证 1 ≤ m ≤ 1 0 4 1 \leq m \le 10^4 1≤m≤104, 1 ≤ t ≤ 1 0 7 1 \leq t \leq 10^7 1≤t≤107,且 1 ≤ m × t ≤ 1 0 7 1 \leq m \times t \leq 10^7 1≤m×t≤107, 1 ≤ a i , b i ≤ 1 0 4 1 \leq a_i, b_i \leq 10^4 1≤ai,bi≤104。
思路
在这个问题中,有一个背包,其容量是时间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 是个天资聪颖的孩子,他的梦想是成为世界上最伟大的医师。为此,他想拜附近最有威望的医师为师。医师为了判断他的资质,给他出了一个难题。医师把他带到一个到处都是草…...
L1-027 出租分数 20
下面是新浪微博上曾经很火的一张图: 一时间网上一片求救声,急问这个怎么破。其实这段代码很简单,index数组就是arr数组的下标,index[0]2 对应 arr[2]1,index[1]0 对应 arr[0]8,index[2]3 对应 arr[3]0&…...
51单片机精进之路-1点亮led灯
本例中led灯使用共阳极连接在电路中,共阳极即将led的正极接在一起,通过上拉电阻接到电源正极,通过单片机io与Led的负极相连,io输出低电平,有电流从led流过,此时led点亮,当io输出高电平时&#x…...
嵌入式学习Day14 C语言 --- 位运算
位运算 注意:符号位也遵循这个规则 一、按位与(&) 运算规则:一假则假 int a 0x33;a & 0x55;0011 00110101 0101 &----------0001 0001 //0x11 二、按位或(|) 运算规则:一真则真 int a 0x33;a |0x55;0011 00110101 0101 |…...
idea设置terminal为git
要在IntelliJ IDEA中设置终端为Git Bash,请按照以下步骤操作: 打开 Settings(设置)。点击 Tools(工具)选项卡。进入 Terminal(终端)界面。在 Shell Path 下选择 Browse(…...
《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+搜索+分布式 基础(持续更新~)
具体操作: day2: 作用: 出现跨域问题 配相对应进行配置即可解决: IDEA连接的,在url最后加参数?useSSLfalse注意链接密码是123(docker中mysql密码) 注意,虚拟机中设置的密码和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应用程序的创建和配置过程,同时提供了很多开箱即用的功能&am…...
SSL协议是什么?关于SSL和TLS的常见问题解答
SSL(安全套接字层)及其后继者TLS(传输层安全)是用于在联网计算机之间建立经过身份验证和加密的链接的协议。尽管SSL协议在 1999年已经随着TLS 1.0的发布而被弃用,但我们仍将这些相关技术称为“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相比,r2021b版本中包含更多集成好的算法模块(尤其是深度学习的模块),想把原来r2015a版本的代码升级到r2021b高版本的Matlab已经采用fitcsvm函数和predict函数替代了旧版本中svmtrain函数和svmclassify函…...
umount:/home/tuners/windows files:目标忙。
您提到的错误信息 "umount: /home/tuners/windows files: 目标忙。" 是在尝试卸载(umount)一个文件系统时常见的错误。这个错误表明有一些进程仍然在使用挂载点(/home/tuners/windows files)下的文件或目录,…...
FPGA_vga显示
一 VGA 1.1 VGA VGA是视频图像阵列,是一种使用模拟信号进行视频传输的标准协议。 1.2 VGA接引脚定义 VGA分公母两种,RGB显示标准。 1.3 VGA显示器 VGA显示器采用图像扫描的方式进行图像显示,将构成图像的像素点,在行同步信号…...
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)
页面配置 页面配置和全局配置的关系: 小程序中,app.json中的window节点,可以全局配置小程序中每个页面的窗口表现 如果某些小程序想要有特殊的窗口表现,可以用页面级别的.json配置文件实现这个需求 页面配置和全局配置冲突时&…...
相机图像质量研究(10)常见问题总结:光学结构对成像的影响--光圈
系列文章目录 相机图像质量研究(1)Camera成像流程介绍 相机图像质量研究(2)ISP专用平台调优介绍 相机图像质量研究(3)图像质量测试介绍 相机图像质量研究(4)常见问题总结:光学结构对成像的影响--焦距 相机图像质量研究(5)常见问题总结:光学结构对成…...
TCP和UDP相关问题(重点)(3)——3.HTTP基于TCP还是UDP?
HTTP/3.0 之前是基于 TCP 协议的,而 HTTP/3.0 将弃用 TCP,改用 基于 UDP 的 QUIC 协议 。具体见HTTP相关问题-CSDN博客...
基于modbus rtu协议操作PLC的EPICS示例
硬件设备 本实验中使用到的设备如下: 1、S7-200 Smart SR20 PLC 作为受控设备,执行机构。 S7-200 Smart是西门子的一款小型PLC产品(以下简称Smart系列)。 Smart系列PLC是西门子公司经过大量调研,为中国小型自动化…...
iOS 26 携众系统重磅更新,但“苹果智能”仍与国行无缘
美国西海岸的夏天,再次被苹果点燃。一年一度的全球开发者大会 WWDC25 如期而至,这不仅是开发者的盛宴,更是全球数亿苹果用户翘首以盼的科技春晚。今年,苹果依旧为我们带来了全家桶式的系统更新,包括 iOS 26、iPadOS 26…...
基于距离变化能量开销动态调整的WSN低功耗拓扑控制开销算法matlab仿真
目录 1.程序功能描述 2.测试软件版本以及运行结果展示 3.核心程序 4.算法仿真参数 5.算法理论概述 6.参考文献 7.完整程序 1.程序功能描述 通过动态调整节点通信的能量开销,平衡网络负载,延长WSN生命周期。具体通过建立基于距离的能量消耗模型&am…...
黑马Mybatis
Mybatis 表现层:页面展示 业务层:逻辑处理 持久层:持久数据化保存 在这里插入图片描述 Mybatis快速入门 。 1. 简介 Nginx 使用 server_name 指令来确定…...
Ascend NPU上适配Step-Audio模型
1 概述 1.1 简述 Step-Audio 是业界首个集语音理解与生成控制一体化的产品级开源实时语音对话系统,支持多语言对话(如 中文,英文,日语),语音情感(如 开心,悲伤)&#x…...
Python如何给视频添加音频和字幕
在Python中,给视频添加音频和字幕可以使用电影文件处理库MoviePy和字幕处理库Subtitles。下面将详细介绍如何使用这些库来实现视频的音频和字幕添加,包括必要的代码示例和详细解释。 环境准备 在开始之前,需要安装以下Python库:…...
Mobile ALOHA全身模仿学习
一、题目 Mobile ALOHA:通过低成本全身远程操作学习双手移动操作 传统模仿学习(Imitation Learning)缺点:聚焦与桌面操作,缺乏通用任务所需的移动性和灵活性 本论文优点:(1)在ALOHA…...
Linux 内存管理实战精讲:核心原理与面试常考点全解析
Linux 内存管理实战精讲:核心原理与面试常考点全解析 Linux 内核内存管理是系统设计中最复杂但也最核心的模块之一。它不仅支撑着虚拟内存机制、物理内存分配、进程隔离与资源复用,还直接决定系统运行的性能与稳定性。无论你是嵌入式开发者、内核调试工…...
uniapp手机号一键登录保姆级教程(包含前端和后端)
目录 前置条件创建uniapp项目并关联uniClound云空间开启一键登录模块并开通一键登录服务编写云函数并上传部署获取手机号流程(第一种) 前端直接调用云函数获取手机号(第三种)后台调用云函数获取手机号 错误码常见问题 前置条件 手机安装有sim卡手机开启…...
