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

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

70 3
71 100
69 1
1 2

输出 #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]$ 时需要的 $dp[j - w_i]$ 依然保存着“上一轮的旧值”（尚未被这一轮的新数据覆盖），完美确保每株草药最多被选择一次（符合 01 背包限制）。

3. 复杂度分析

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

样例验证

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

以一维 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;
          }
      }
  }

推荐练习

掌握了 01 背包和完全背包这两个基础模型，就为后续学习多重背包、分组背包等更复杂的 DP 问题打下了坚实基础。

本文由coderli.com原创，按照CC BY-NC-SA 4.0 进行授权

所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code

“luogu-”系列题目可在 洛谷题库 在线评测。

“bcqm-”系列题目可在 编程启蒙题库 在线评测。

GESP/CSP认证交流QQ群： 688906745

GESP/CSP 认证学习微信公众号