OneCoder Avatar
OneCodercoderli.com · 1023 篇博文
⌘ NOIP

NOIP 全国联赛真题

🎨 视觉封面

【NOIP真题】2005 采药 luogu-P1048 | 适用于 GESP六级 / CSP-J 练习

📅 2026-09-27·✍️ OneCoder·计算中...·⏱️ 13 分钟

在限定的时间或负重预算下,面对一系列各具耗时与价值且不可分割的物品,如何做出取舍以达成总体收益最大化?洛谷 P1048 [NOIP2005 普及组]《采药》是整个动态规划领域中**01 背包模型(0/1 Knapsack Problem)**无可争议的“Hello World”基石之作。题目要求采药人在有限的 时间内采集草药,每株草药只能采摘一次。从二维子结构递推状态定义,到倒序遍历消除后效性的“一维滚动数组”空间优化压缩,本题是 GESP 六级考生由搜索递推进阶到现代动态规划殿堂的启蒙法宝。

luogu-P1048 [NOIP2005 普及组] 采药

🔗 洛谷原题传送门:luogu-P1048 [NOIP2005 普及组] 采药

题目描述

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

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

输入格式

第一行有 个整数 ()和 (),用一个空格隔开, 代表总共能够用来采药的时间, 代表山洞里的草药的数目。

接下来的 行每行包括两个在 到 之间(包括 和 )的整数,分别表示采摘某株草药的时间和这株草药的价值。

输出格式

输出在规定的时间内可以采到的草药的最大总价值。

输入输出样例

输入 #1

Code4 行
70 3
71 100
69 1
1 2

输出 #1

Code1 行
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)状态转移方程

对于第 株草药(耗时 ,价值 ),面临两种抉择:

  1. 不采第 株草药: 此时总价值完全继承前 株草药在容量 下的最优解:
  2. 采第 株草药(前提是当前时间容量 ): 必须为它预留出 的耗时空间。在前 株草药中使用剩余时间 获得的最大价值加上这株草药的价值 :

综合两种决策分支,取最大值:

4. 空间极致优化:一维滚动数组与逆序遍历

如果直接使用二维数组,空间开销为 。在本题中 ,二维数组仅占用约 内存,虽然空间完全充裕,但在更高阶算法题或硬件严格受限的环境下,空间优化至关重要。

(1)降维的核心观察

观察二维状态转移方程: 计算第 轮的所有状态时,仅仅依赖上一轮(第 轮)的状态值,更早的第 轮的历史数据已完成使命,无需长期驻留。

因此,我们可以直接省去物品维度 ,只保留时间容量维度 ,用一维数组 dp[j] 滚动记录最优价值。

(2)为什么内层循环必须“倒序逆推”?

这是背包动态规划中最经典、最核心的考点,也是初学者极易踩坑的地方!

假设我们在更新当前第 株草药时,时间容量 采用正序遍历(从 到 ):

Code3 行
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)。

而如果采用倒序逆推(从 递减到 ):

Code3 行
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. 易错点与边界防坑指南

  1. 内层循环下界设置:
    • 倒序遍历的终止条件是 j >= w,不可漏写或误写为 j >= 0;如果误写为 j >= 0 且未做保护,会导致 j - w 下标越界访问负数非法内存。
  2. 输入顺序与变量混淆:
    • 第一行输入的是 和 ( 为总时间上限, 为草药总数);
    • 后续每行先输入采摘耗时 ,再输入价值 。切勿将时间与价值的变量顺序颠倒。
  3. 空间安全与数据类型:
    • ,一维数组长度开到 1005,常数极小,执行速度极快;
    • 最大理论总价值为 ,32 位带符号整型 int 范围约为 ,完全在安全范围内,无需引入 long long。

6. 复杂度深度剖析

  • 时间复杂度: 外层循环遍历 株草药,内层循环逆序遍历时间容量,步数为 。 总操作次数为: 对于最大数据规模 ,总运算量约为 次操作,在现代评测机上仅需不到 即可秒杀,远低于 的时间限制。
  • 空间复杂度: 采用一维滚动数组后,空间开销严格为: 只需一个长度为 的 int 数组,占用内存约为 ,相比于题目限制的 ,几乎可以忽略不计。

完整参考代码 (C++11)

C++43 行
/**
 * 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;
}
看完题解去实战!OneCoder C++ 信奥远征闯关平台 (oi.coderli.com)
💡 OneCoder 资源指引

所有代码开源上传至 GitHub:yummy-code 仓库 · GESP 专题站:GESP WIKI

🤝 技术交流与答疑

欢迎加入:C++ GESP/CSP 考级答疑群(688906745) 与 Java/Python交流群(982860385),点击可直接加群。

📚

猜你想读 · 相关文章推荐

CSP / NOIP 信奥竞赛 · NOIP⏱️ 10 分钟

【NOIP真题】2001 装箱问题 luogu-P1049 | 适用于 GESP六级 / CSP-J 练习

日常生活中打包行李或装载货箱,我们总希望能把有限的箱子空间填得越满越好。洛谷 P1049 [NOIP2001 普及组]《装箱问题》看似在问“剩余空间最小化”,但本质上却是一个将物品体积等价转化为物品价值的经典 01 背包变种模型。既然目标是让剩余空间 V - w 最小,...

阅读全文 →
CSP / NOIP 信奥竞赛 · NOIP⏱️ 12 分钟

【NOIP真题】2006 开心的金明 luogu-P1060 | 适用于 GESP六级 / CSP-J 练习

面对手头的固定预算和心仪物品的清单,每一件物品既有本身的价格,又有主观的喜爱重要度,如何在预算硬约束下让“开心程度”达到顶峰?洛谷 P1060 [NOIP2006 普及组]《开心的金明》生动刻画了现实消费中的多属性权衡决策。题目的数学本质依然是 01 背包,但其精妙之处...

阅读全文 →
CSP / NOIP 信奥竞赛 · NOIP⏱️ 15 分钟

【NOIP真题】2004 合唱队形 luogu-P1091 | 适用于 GESP六级 / CSP-J 练习

排练合唱队形时,如何让队列呈现先严格递增、后严格递减的“山峰形(单峰形)”,同时移走尽可能少的同学?洛谷 P1091 [NOIP2004 提高组]《合唱队形》是线性动态规划中双向最长上升子序列(Double LIS)的传世经典。题目要求“移走人数最少”,反向思考即为“保...

阅读全文 →
OneCoder

OneCoder

一个中年人的自留地,记录学习 C++、GESP/NOI、Java、Python 与算法架构的心得体会。本站唯一网址:coderli.com

读者讨论与留言

共 0 条讨论
邮箱必填 · 支持 Markdown 格式与直接回复
💬 还没有读者留言,快来成为第一个讨论者吧!