【NOIP】2005真题解析 luogu-P1048 采药（适合GESP六级以上练习）

发表于 2026/07/12 更新于 2026/07/12

作者 OneCoder

次浏览 14 分钟阅读

NOIP 2005 普及组真题，01 背包问题的经典入门题。每株草药只能采或不采（选或不选），在有限的时间内使采到的草药总价值最大。适合GESP六级以上考生练习。题目难度⭐⭐，洛谷难度等级普及-。

luogu-P1048 [NOIP 2005 普及组] 采药

题目要求

题目描述

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

输入格式

第一行有 $2$ 个整数 $T$（$1 \le T \le 1000$）和 $M$（$1 \le M \le 100$），用一个空格隔开，$T$ 代表总共能够用来采药的时间，$M$ 代表山洞里的草药的数目。
接下来的 $M$ 行每行包括两个在 $1$ 到 $100$ 之间（包括 $1$ 和 $100$）的整数，分别表示采摘某株草药的时间和这株草药的价值。

输出格式

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

输入输出样例 #1

输入 #1

输出 #1

3

说明/提示

数据范围

对于 $30\%$ 的数据，$M \le 10$
对于全部的数据，$M \le 100$

题目来源

NOIP 2005 普及组第三题

题目分析

本题是最经典的 01 背包问题。将采药的场景翻译为背包模型：

背包容量 $\rightarrow$ 总时间 $T$
物品 $\rightarrow$ 每株草药
物品重量 $\rightarrow$ 采摘该株草药所需的时间 $w_i$
物品价值 $\rightarrow$ 该株草药的价值 $v_i$
选择限制 $\rightarrow$ 每株草药只有一株，最多只能选一次（要么选，要么不选，即 0 或 1）

下面我们分别介绍二维 DP 和一维 DP 两种解法，它们从最直观的推导逐步过渡到空间上的极致优化。

解法一：最直观的二维 DP 算法

1. 状态定义

用二维数组 $dp[i][j]$ 表示：只考虑前 $i$ 株草药，在总容量（总时间）限制为 $j$ 的情况下，能获得的最大总价值。

2. 状态转移方程

对于第 $i$ 株草药（耗时 $w_i$，价值 $v_i$），对每个总容量 $j$：

如果装不下（$j < w_i$）：超重了无法采摘，价值和上一轮保持一致。 $dp[i][j] = dp[i-1][j]$
如果装得下（$j \ge w_i$）：我们可以选择“不采”或“采”，取价值最大者。 $dp[i][j] = \max(dp[i-1][j],\ dp[i-1][j - w_i] + v_i)$

3. 初始状态与边界

初始状态：$dp[0][j] = 0$，表示不考虑任何草药时价值为 $0$。
最终答案：$dp[M][T]$，即考虑全部 $M$ 株草药，总容量限制为 $T$ 时的最优解。

4. 复杂度分析

时间复杂度：$O(M \times T)$
空间复杂度：$O(M \times T)$

解法二：空间优化的一维 DP 算法（滚动数组）

1. 优化原理

观察二维状态转移方程：计算第 $i$ 行状态时，我们只依赖于上一行 $dp[i-1]$ 的数据，更早的历史记录无需保留。因此，我们可以将二维数组压缩成一维数组 $dp[j]$，代表：在总时间限制为 $j$ 的情况下，能采到的草药的最大总价值。

2. 状态转移方程

对于每一株草药 $i$，我们从大到小（逆序）遍历时间 $j$（从 $T$ 递减到 $w_i$）： $dp[j] = \max(dp[j],\ dp[j - w_i] + v_i)$

逆序遍历的精妙之处：因为从大到小更新，算 $dp[j]$ 时需要的 $dp[j - w_i]$ 依然保存着“上一轮的旧值”（尚未被这一轮的新数据覆盖），完美确保每株草药最多被选择一次（符合 01 背包限制）。

3. 复杂度分析

时间复杂度：$O(M \times T)$，双层循环。$M \le 100, T \le 1000$，运算次数最多 $10^5$，非常快。
空间复杂度：$O(T)$，一维滚动数组。

样例验证

样例输入：$T = 70, M = 3$

草药编号	采摘时间 $w$	价值 $v$
$1$	$71$	$100$
$2$	$69$	$1$
$3$	$1$	$2$

以一维 DP 的运行流程为例：

初始状态：$dp$ 数组全为 $0$。
处理草药 $1$（$w=71, v=100$）：由于 $w > T = 70$，内层循环不满足 $j \ge w_i$ 条件，无任何更新。
处理草药 $2$（$w=69, v=1$）：只有 $j \ge 69$ 时被更新为 $1$，即 $dp[69] = 1, dp[70] = 1$。
处理草药 $3$（$w=1, v=2$）：从大到小更新：
- $dp[70] = \max(dp[70], dp[69] + 2) = \max(1, 1 + 2) = 3$
- $dp[69] = \max(dp[69], dp[68] + 2) = \max(1, 0 + 2) = 2$
- ……
- $dp[1] = \max(dp[1], dp[0] + 2) = \max(0, 0 + 2) = 2$

最终 $dp[70] = 3$，对应选择草药 $2$（价值 $1$）和草药 $3$（价值 $2$），结果与样例完全一致。

示例代码

方法一：二维 DP（最直观的写法）

二维 DP 写法最契合递推逻辑，通过直接查表上一行的数据进行决策。虽然空间开销稍大，但逻辑最为清晰易懂。

  
#include <iostream>
#include <algorithm>

// dp[i][j] 表示：只考虑前 i 株草药，在假设背包容量（总时间）为 j 时的最大价值
int dp[105][1005];

// 存储每株草药的采摘时间（重量）和价值
int w[105], v[105];

int main() {
    int T, M;
    std::cin >> T >> M;

    // 读入所有草药的重量（时间）和价值
    for (int i = 1; i <= M; i++) {
        std::cin >> w[i] >> v[i];
    }

    // 初始化：由于全局变量默认初始值为 0，dp[0][j] 全为 0，代表没有任何草药可选时价值为 0

    // 外层循环：依次考虑前 1 ~ M 株草药
    for (int i = 1; i <= M; i++) {
        // 内层循环：枚举假设的背包总容量 j（从最小容量 0 到最大可用时间 T）
        for (int j = 0; j <= T; j++) {
            // 默认不选第 i 株草药：继承只考虑前 i-1 株草药、容量为 j 时的最大价值
            dp[i][j] = dp[i - 1][j];

            // 如果假设的容量 j 足够装下第 i 株草药，尝试进行采摘决策
            if (j >= w[i]) {
                // 在“不采摘”（dp[i-1][j]）和“采摘”（前 i-1 株在剩余容量 j-w[i] 下的最优价值 + 当前草药价值 v[i]）中取最大值
                dp[i][j] = std::max(dp[i][j], dp[i - 1][j - w[i]] + v[i]);
            }
        }
    }

    // dp[M][T] 即为在总时间 T 内，考虑全部 M 株草药能采摘到的最大价值
    std::cout << dp[M][T] << std::endl;
    return 0;
}

方法二：一维 DP（空间优化版）

由于计算当前行仅依赖上一行的数据，我们可以将二维表压缩到一维，在原数组上直接覆盖更新。通过逆序（从大到小）遍历容量，确保每件草药只被采摘选择一次。

  
#include <iostream>
#include <algorithm>

// dp[j] 表示：在总时间（总容量）限制为 j 的情况下的最大最优价值
int dp[1005];

int main() {
    int T, M;
    std::cin >> T >> M;

    // 依次读入并处理每一株草药
    for (int i = 0; i < M; i++) {
        int w, v;
        std::cin >> w >> v;

        // 逆序（从大到小）遍历假设的总容量 j
        // 注意：只需递减到 w 即可（当容量比当前草药重量还小时，无法放入，状态直接保持不变）
        for (int j = T; j >= w; j--) {
            // 决策核心：我们在“不采摘当前草药”（保持原有的最优值 dp[j]）
            // 和“采摘当前草药”（上一轮尚未被更新的旧状态 dp[j - w] 加上当前草药价值 v）中取最大值
            dp[j] = std::max(dp[j], dp[j - w] + v);
        }
    }

    // dp[T] 即为在总时间 T 限制下的最大总价值
    std::cout << dp[T] << std::endl;
    return 0;
}

拓展思考

01 背包与完全背包的代码对比

将本题（01 背包）和 B2174（完全背包）的核心代码放在一起，差异一目了然：

  for (int i = 0; i < n; i++) {
      int w, v;
      std::cin >> w >> v;
-     // 完全背包：正序遍历，允许重复选取
-     for (int j = w; j <= V; j++) {
+     // 01 背包：逆序遍历，每件物品最多选一次
+     for (int j = T; j >= w; j--) {
          if (dp[j - w] + v > dp[j]) {
              dp[j] = dp[j - w] + v;
          }
      }
  }

题目	类型	要点
B2174 完全背包	完全背包	正序遍历，每种物品可选无限件
P1048 采药（本题）	01 背包	逆序遍历，每件物品最多选一次
P5662 纪念品	完全背包应用	多天交易转化为每日独立的完全背包
P17012 条形蛋糕	一维 DP / 完全背包	切割问题，完全背包的等价建模

【NOIP】2005真题解析 luogu-P1048 采药（适合GESP六级以上练习）

luogu-P1048 [NOIP 2005 普及组] 采药

题目要求

题目描述

输入格式

输出格式

输入输出样例 #1

输入 #1

输出 #1

说明/提示

数据范围

题目来源

题目分析

解法一：最直观的二维 DP 算法

1. 状态定义

2. 状态转移方程

3. 初始状态与边界

4. 复杂度分析

解法二：空间优化的一维 DP 算法（滚动数组）

1. 优化原理

2. 状态转移方程

3. 复杂度分析

样例验证

示例代码

方法一：二维 DP（最直观的写法）

方法二：一维 DP（空间优化版）

拓展思考

01 背包与完全背包的代码对比

推荐练习

热门标签