NOIP 全国联赛真题
🎨 视觉封面【NOIP真题】2005 采药 luogu-P1048 | 适用于 GESP六级 / CSP-J 练习
在限定的时间或负重预算下,面对一系列各具耗时与价值且不可分割的物品,如何做出取舍以达成总体收益最大化?洛谷 P1048 [NOIP2005 普及组]《采药》是整个动态规划领域中**01 背包模型(0/1 Knapsack Problem)**无可争议的“Hello World”基石之作。题目要求采药人在有限的 时间内采集草药,每株草药只能采摘一次。从二维子结构递推状态定义,到倒序遍历消除后效性的“一维滚动数组”空间优化压缩,本题是 GESP 六级考生由搜索递推进阶到现代动态规划殿堂的启蒙法宝。
luogu-P1048 [NOIP2005 普及组] 采药
🔗 洛谷原题传送门:luogu-P1048 [NOIP2005 普及组] 采药
题目描述
辰辰是个天资聪颖的孩子,他的梦想是成为世界上最伟大的医师。为此,他想拜附近最有威望的医师为师。医师为了判断他的资质,给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说:“孩子,这个山洞里有一些不同的草药,采每一株都需要一些时间,每一株也有它自身的价值。我会给你一段时间,在这段时间里,你可以采到一些草药。如果你是一个聪明的孩子,你应该可以让采到的草药的总价值最大。”
如果你是辰辰,你能完成这个任务吗?
输入格式
第一行有 个整数 ()和 (),用一个空格隔开, 代表总共能够用来采药的时间, 代表山洞里的草药的数目。
接下来的 行每行包括两个在 到 之间(包括 和 )的整数,分别表示采摘某株草药的时间和这株草药的价值。
输出格式
输出在规定的时间内可以采到的草药的最大总价值。
输入输出样例
输入 #1
70 3
71 100
69 1
1 2输出 #1
3说明/提示
【数据范围】
- 对于 的数据,;
- 对于全部的数据,。
【题目来源】
NOIP 2005 普及组第三题
题目深度剖析
1. 0/1 背包模型的抽象与本质
在算法学习中,我们常常面临“资源有限、需求离散、收益最大化”的决策问题。本题正是算法界最具代表性的经典模型——**0/1 背包问题(0-1 Knapsack Problem)**的标准原型。
我们可以将题目的要素与经典背包模型进行一一映射:
- 背包总容量:对应采药的总时间限制 。
- 可选物品总数:对应山洞里的草药总数 。
- 物品重量 / 耗费(Cost):对应采摘某株草药所消耗的时间 。
- 物品收益 / 价值(Value):对应这株草药自身的价值 。
- “0/1”的数学含义:每株草药只有两种状态——要么采(取 次),要么不采(取 次),无法切割分成部分,也不允许重复选取。
2. 为什么贪心策略(按性价比排序)必然失效?
不少初学者在第一次接触背包问题时,往往直觉会尝试贪心算法:
- 策略一:每次挑价值最大的草药采(价值优先);
- 策略二:每次挑耗时最短的草药采(时间优先);
- 策略三:计算每株草药的“性价比”(即单位时间价值 ),按性价比从高到低贪心选取。
然而,在离散不可分割的 0/1 背包中,即使是性价比贪心策略依然可能彻底失效!
我们来看一个经典反例: 设总时间限制 ,现有三株草药:
- 草药 A:耗时 ,价值 ,性价比为 ;
- 草药 B:耗时 ,价值 ,性价比为 ;
- 草药 C:耗时 ,价值 ,性价比为 。
若按性价比贪心排序,优先采草药 A(耗时 ,剩余可用时间仅剩 )。此时剩余时间不足以采摘 B 或 C 中的任何一株,最终总收获价值为 。 但全局最优选择显然是完全放弃性价比最高的 A,转而采摘草药 B 和 C:总耗时 ,获得总价值高达 !
贪心之所以失败,是因为选取了局部看似高收益的单件物品后,造成的“时间碎片”(容量浪费),其负面损失超过了单件物品的微弱收益。因此,唯有通过全局动态规划系统地权衡“选”与“不选”的累积效应,才能保证得到全局最优解。
3. 二维动态规划:状态定义与转移方程
(1)状态定义
设二维状态数组 dp[i][j] 表示:
只考虑前 株草药,在总采药时间限制不超过 的情况下,能够获取的最大草药总价值。 其中 ,。
(2)边界与初始状态
- 当没有草药可选时(),无论时间上限 是多少,最大价值均为 :
dp[0][j] = 0; - 当时间上限为 时(),无法采摘任何草药,最大价值均为 :
dp[i][0] = 0。 全局变量在 C++ 中自动初始化为 ,天然满足初始边界条件。
(3)状态转移方程
对于第 株草药(耗时 ,价值 ),面临两种抉择:
- 不采第 株草药: 此时总价值完全继承前 株草药在容量 下的最优解:
- 采第 株草药(前提是当前时间容量 ): 必须为它预留出 的耗时空间。在前 株草药中使用剩余时间 获得的最大价值加上这株草药的价值 :
综合两种决策分支,取最大值:
4. 空间极致优化:一维滚动数组与逆序遍历
如果直接使用二维数组,空间开销为 。在本题中 ,二维数组仅占用约 内存,虽然空间完全充裕,但在更高阶算法题或硬件严格受限的环境下,空间优化至关重要。
(1)降维的核心观察
观察二维状态转移方程: 计算第 轮的所有状态时,仅仅依赖上一轮(第 轮)的状态值,更早的第 轮的历史数据已完成使命,无需长期驻留。
因此,我们可以直接省去物品维度 ,只保留时间容量维度 ,用一维数组 dp[j] 滚动记录最优价值。
(2)为什么内层循环必须“倒序逆推”?
这是背包动态规划中最经典、最核心的考点,也是初学者极易踩坑的地方!
假设我们在更新当前第 株草药时,时间容量 采用正序遍历(从 到 ):
for (int j = w_i; j <= T; ++j) {
dp[j] = max(dp[j], dp[j - w_i] + v_i);
}当更新到较大的 时,它依赖的 dp[j - w_i] 已经在前面的较小步数中被当前第 株草药更新过了!
也就是说,dp[j - w_i] 中已经包含了第 株草药的贡献,再加上一次 ,就意味着同一株草药被重复采摘了多次!这就变成了后续将要学习的“完全背包问题”(P1616)。
而如果采用倒序逆推(从 递减到 ):
for (int j = T; j >= w_i; --j) {
dp[j] = max(dp[j], dp[j - w_i] + v_i);
}因为是从大到小更新,当我们计算 dp[j] 时,所引用的 dp[j - w_i] 位于当前位置的左侧,它还没有被本轮(第 株草药)修改过,仍然完好保存着上一轮(前 株草药)的历史最优解!
这就严格保证了每株草药至多只会被采摘一次(严格满足 0/1 约束)。
并且,当 时,容量不足以采摘当前草药,dp[j] 直接保持原值不变,因此内层循环只需递减到 即可自然终止,无需额外的 if (j >= w_i) 条件判断。
5. 易错点与边界防坑指南
- 内层循环下界设置:
- 倒序遍历的终止条件是
j >= w,不可漏写或误写为j >= 0;如果误写为j >= 0且未做保护,会导致j - w下标越界访问负数非法内存。
- 倒序遍历的终止条件是
- 输入顺序与变量混淆:
- 第一行输入的是 和 ( 为总时间上限, 为草药总数);
- 后续每行先输入采摘耗时 ,再输入价值 。切勿将时间与价值的变量顺序颠倒。
- 空间安全与数据类型:
- ,一维数组长度开到
1005,常数极小,执行速度极快; - 最大理论总价值为 ,32 位带符号整型
int范围约为 ,完全在安全范围内,无需引入long long。
- ,一维数组长度开到
6. 复杂度深度剖析
- 时间复杂度: 外层循环遍历 株草药,内层循环逆序遍历时间容量,步数为 。 总操作次数为: 对于最大数据规模 ,总运算量约为 次操作,在现代评测机上仅需不到 即可秒杀,远低于 的时间限制。
- 空间复杂度:
采用一维滚动数组后,空间开销严格为:
只需一个长度为 的
int数组,占用内存约为 ,相比于题目限制的 ,几乎可以忽略不计。
完整参考代码 (C++11)
/**
* Problem: luogu-P1048 [NOIP2005 普及组] 采药
* Algorithm: 基础动态规划 (0/1 背包问题 · 一维滚动数组空间优化)
* Standard: C++11 (CCF GESP / CSP-J 官方规范)
* Author: OneCoder
*/
#include <iostream>
#include <algorithm>
using namespace std;
// 最大时间上限为 1000,数组预留安全裕量
const int MAXT = 1005;
// 一维滚动数组:dp[j] 表示在采药总时间不超过 j 的约束下,所能获得的最大草药总价值
int dp[MAXT];
int main() {
int T, M;
// 读入采药的总时间限制 T 和山洞中草药的数目 M
cin >> T >> M;
// 依次处理每一株草药(外层循环遍历物品)
for (int i = 1; i <= M; ++i) {
int w, v;
// 读入当前草药采摘所耗费的时间 w 和草药自身的价值 v
cin >> w >> v;
// 0/1 背包空间优化的核心:倒序逆推可用时间容量 j
// 必须从最大时间 T 倒序递减至当前草药的耗时 w
// 倒序能严格保证计算 dp[j] 时,所引用的 dp[j - w] 依然是上一轮未放入当前草药的旧状态
// 从而确保每株草药至多只被采摘一次
for (int j = T; j >= w; --j) {
dp[j] = max(dp[j], dp[j - w] + v);
}
}
// 最终 dp[T] 即为在总时间 T 的限制下能够采得的最大草药总价值
cout << dp[T] << "\n";
return 0;
}所有代码开源上传至 GitHub:yummy-code 仓库 · GESP 专题站:GESP WIKI
欢迎加入:C++ GESP/CSP 考级答疑群(688906745) 与 Java/Python交流群(982860385),点击可直接加群。
猜你想读 · 相关文章推荐
【NOIP真题】2001 装箱问题 luogu-P1049 | 适用于 GESP六级 / CSP-J 练习
日常生活中打包行李或装载货箱,我们总希望能把有限的箱子空间填得越满越好。洛谷 P1049 [NOIP2001 普及组]《装箱问题》看似在问“剩余空间最小化”,但本质上却是一个将物品体积等价转化为物品价值的经典 01 背包变种模型。既然目标是让剩余空间 V - w 最小,...
【NOIP真题】2006 开心的金明 luogu-P1060 | 适用于 GESP六级 / CSP-J 练习
面对手头的固定预算和心仪物品的清单,每一件物品既有本身的价格,又有主观的喜爱重要度,如何在预算硬约束下让“开心程度”达到顶峰?洛谷 P1060 [NOIP2006 普及组]《开心的金明》生动刻画了现实消费中的多属性权衡决策。题目的数学本质依然是 01 背包,但其精妙之处...
【NOIP真题】2004 合唱队形 luogu-P1091 | 适用于 GESP六级 / CSP-J 练习
排练合唱队形时,如何让队列呈现先严格递增、后严格递减的“山峰形(单峰形)”,同时移走尽可能少的同学?洛谷 P1091 [NOIP2004 提高组]《合唱队形》是线性动态规划中双向最长上升子序列(Double LIS)的传世经典。题目要求“移走人数最少”,反向思考即为“保...
OneCoder
一个中年人的自留地,记录学习 C++、GESP/NOI、Java、Python 与算法架构的心得体会。本站唯一网址:coderli.com

