洛谷 P1048 采药 - Solution

1. 题目数据 (Problem Metadata)

题目类型：传统题
题目链接：https://www.luogu.com.cn/problem/P1048
时间限制：1.00s
内存限制：125.00MB

2. 题意简述 (Problem Summary)

给定总时间 $T$（$1 \le T \le 1000$）和 $M$ 株草药（$1 \le M \le 100$）。每株草药 $i$ 需要采摘时间 $t_i$ 且具有价值 $v_i$（$1 \le t_i, v_i \le 100$）。求在总时间不超过 $T$ 的前提下，能够获得的最大总价值。

本质是 0/1 背包问题：$M$ 个物品，背包容量为 $T$，物品 $i$ 重量 $t_i$、价值 $v_i$，每个物品只能选一次，最大化总价值。

3. 朴素解法 (Brute-Force)

枚举每株草药的"采/不采"，共 $2^M$ 种方案，对每种合法方案求和取最大。时间复杂度 $O(2^M)$。

本题 $M \le 100$，$2^{100}$ 远超任何实际时限，即使 $M \le 10$ 的子任务（$2^{10} = 1024$）勉强可过，但满数据下即使再怎么剪枝也完全不可行。需要更高效的做法。

4. 核心解法 (Main Solution)

特殊性质：问题具有最优子结构——前 $i$ 个物品的最优解可由前 $i-1$ 个物品的最优解递推得到。同时，状态转移仅依赖上一阶段，具有无后效性。因此可用动态规划求解。
关键突破：将"枚举所有子集"转化为"按物品逐个决策"。设 $dp[i][j]$ 表示考虑前 $i$ 株草药、总用时不超过 $j$ 时的最大价值，则每次只需决定第 $i$ 株是采还是不采。
推导过程：

定义 $dp[i][j]$ 为前 $i$ 株草药在总用时不超过 $j$ 的条件下可获得的最大价值。

不采第 $i$ 株：价值继承前 $i-1$ 株的结果，$dp[i][j] = dp[i-1][j]$。

采第 $i$ 株：需预留 $t_i$ 的时间，$dp[i][j] = dp[i-1][j - t_i] + v_i$（前提 $j \ge t_i$）。

两者取最大，得到状态转移方程：$$dp[i][j] = \max\big(dp[i-1][j],\ dp[i-1][j - t_i] + v_i\big) \quad (j \ge t_i)$$
当 $j < t_i$ 时，无法采摘第 $i$ 株，$dp[i][j] = dp[i-1][j]$。

空间优化（滚动数组）：观察转移方程，$dp[i][\cdot]$ 仅依赖 $dp[i-1][\cdot]$，因此可以去掉第一维。但注意：更新 $dp[j]$ 时需要用到旧的 $dp[j - t_i]$（即上一轮的 $i-1$ 状态），若 $j$ 从小到大遍历，$dp[j - t_i]$ 可能已被本轮更新覆盖，导致同一物品被多次选用（变成完全背包）。因此必须倒序遍历 $j$（从 $T$ 到 $t_i$），保证 $dp[j - t_i]$ 仍是上一轮的值： $$dp[j] = \max\big(dp[j],\ dp[j - t_i] + v_i\big) \quad (j = T, T-1, \dots, t_i)$$
使用奇偶法滚动数组优化也可，但本题使用倒序法更简单。
初始 $dp[0 \dots T] = 0$，最终答案为 $dp[T]$。

5. 正确性证明 (Proof of Correctness)

最优子结构：假设前 $i$ 株草药、容量 $j$ 的最优方案为 $S$。若 $S$ 不包含第 $i$ 株，则 $S$ 也是前 $i-1$ 株、容量 $j$ 的最优方案（否则可替换为更优方案）。若 $S$ 包含第 $i$ 株，去掉它后得到前 $i-1$ 株、容量 $j - t_i$ 的方案，该方案也必为最优（否则原方案非最优）。两种情况下子问题最优解均蕴含于原问题最优解中，满足最优子结构。

无后效性：将物品编号 $i$ 视为阶段，第 $i$ 阶段的状态仅由第 $i-1$ 阶段转移而来，与 $i+1$ 及之后的阶段无关。因此 DP 递推有效。

空间优化（倒序遍历）的正确性，上文已经证明。

6. 复杂度分析 (Complexity)

时间复杂度：$O(MT)$。外层循环 $M$ 次，内层循环至多 $T$ 次，每次转移 $O(1)$。本题 $M \le 100$，$T \le 1000$，运算量约 $10^5$ 级别，在年代久远的评测机上也可在 1 秒内完成。
空间复杂度：一维优化后为 $O(T)$，即 $dp$ 数组大小。本题 $T \le 1000$，占用内存约 4 KB，远小于通常的 128 MB 限制。

7. 实现细节与避坑指南 (Implementation Details)

倒序遍历是核心：0/1 背包空间优化中，$j$ 必须从大到小遍历。若写成正序 for (int j = 0; j <= T; j++)，等价于完全背包，每株草药可无限次采摘，答案必然错误。
数组大小：$dp$ 数组至少开到 $T_{\max} = 1000$，建议多开几个（如 $1005$），防止 off-by-one。
初始化：全部赋 $0$ 即可（不要求恰好装满，只要求不超过容量）。
循环边界条件：注意 j >= t[i]，以防止数组越界问题。

8. 参考代码 (Reference Code)

#include <iostream>
#include <algorithm>
using namespace std;

const int MAXT = 1005;
int T, M, t[MAXT], v[MAXT];
int dp[MAXT];

int main() {
    cin >> T >> M;
    for (int i = 1; i <= M; i++)
        cin >> t[i] >> v[i];

    for (int i = 1; i <= M; i++)
        for (int j = T; j >= t[i]; j--)       // 倒序 + 注意边界
            dp[j] = max(dp[j], dp[j - t[i]] + v[i]);

    cout << dp[T] << endl;
    return 0;
}

9. 补充说明 (Additional Notes)

经典问题定位：本题是 0/1 背包问题的标准模板题，也是 NOIP 历史上最经典的 DP 入门题之一。2005 年作为普及组第三题出现，至今仍是无数 OIer 学习动态规划的第一道题。

变种：

若每种草药可无限采摘，将内层循环改为正序即得完全背包。
若要求"恰好装满"时间 $T$，需将 $dp[1 \dots T]$ 初始化为 $-\infty$，仅 $dp[0] = 0$。

拓展习题：

洛谷 P2871 [USACO07DEC] Charm Bracelet S — 0/1 背包英文裸题，数据范围更大，必须使用一维优化。
洛谷 P1049 [NOIP2001 普及组] 装箱问题 — 0/1 背包变种（物品价值 = 自身体积，求最小剩余空间），用完全相同的 DP 框架可解。
洛谷 P1616 疯狂的采药 — 本题的完全背包版本（每种草药无限采），只需将内层循环改为正序。