第一次看到P1048采药这道题的时候，我的第一反应是：这不就是个普通的最优化问题吗？山洞里有M株草药，每株采摘需要一定时间，也有对应价值，在总时间T的限制内，怎么选才能让采到的总价值最大。直觉上会想到贪心——按价值/时间比排序，先采“性价比”高的。但稍微一琢磨就会发现，贪心在这里并不可靠。

后来我才意识到，这道题是国内竞赛圈里最经典的动态规划入门题之一，考察的模型正是01背包。它适合每一个刚开始学DP的人去反复拆解：状态怎么定义、转移方程怎么来、二维数组怎么优化成一维、循环为什么要倒着写。这篇文章我不打算只贴一个AC代码，而是想把从读题到建模、从二维DP到手推样例、从滚动数组到常见坑位，整条链路都捋一遍。哪怕你是刚接触背包问题的小白，看完也能把这道题彻底吃透。

1. 读题三件事：时间、草药、价值，怎么映射成背包三要素

1.1 为什么“采药”天然是背包问题

先来看一个反直觉的例子。假设总时间T=10，有两株药，A耗时6价值8，B耗时5价值6。按“性价比”排序，A是8/6约等于1.33，B是6/5等于1.2，先选A的话剩下4单位时间，采不了B，总价值8；可如果先选B，剩下5单位时间也采不了A，总价值6。这种例子还不足以说明问题，再看一组：T=10，C耗时6价值8，D耗时5价值5，E耗时5价值5。性价比最高的仍是C，但选了C之后剩余4，什么都采不了，总价值8；如果放弃C，同时选D和E，耗时刚好10，总价值10，这才是正确答案。

这就是典型的“组合决策”问题：每个物品的取舍不是独立可加总比较的，而是互相挤占容量。贪心算法只能应对“可分割”的资源分配，一旦变成“要么全拿要么全不拿”，就必须交给动态规划来处理。背包问题有三个核心要素：容量、物品重量、物品价值。放到这道题里，总时间T就是背包容量，每株草药的采摘耗时就是物品重量，草药的价值就是物品价值，每株只能选择一次，这就是“01”的由来——0代表不选，1代表选。

我刚开始学的时候，总觉得“建模”这个词很玄乎。但其实建模就干一件事：把题目里的名词翻译成你熟悉的算法模型里的名词。你只要能把“时间”看成“容量”，把“采药”看成“装物品”，这道题就已经做完了一半。

1.2 T和M的数据范围告诉了我们什么

这道题的约束非常短：T在1到1000之间，M在1到100之间。这两句信息量很大，直接决定了解法的时间复杂度预期和内存使用。

T最大1000，M最大100，最简单的状态设计是开一个dp[M+1][T+1]的二维数组，也就是最多101乘1001个int，大概10万个整数，在C++里也就400KB左右的内存，随便分配。时间复杂度是O(M×T)，最坏10万次状态转移，在评测环境里连1毫秒都用不到。所以在数据范围不紧张的前提下，用朴素的二维DP就能稳稳通过。

但这个数据范围也给了很多人一个错觉：既然M和T都不大，暴力枚举行不行？每株草药有“采”和“不采”两种选择，M最大100，那就是2的100次方种组合，这个数字大到完全没有可行性，所以暴力枚举子集的思路必须尽早放弃。记忆化搜索虽然可以写出AC代码，但它的调用栈开销和递归深度在更复杂的背包题里会成为隐患，不如从一开始就练成递推DP的习惯。我个人的判断标准很简单：看到“每件物品只能选一次”“在容量限制下最大化价值”，直接进入背包模型，不要和暴力枚举纠缠。

2. 二维DP跑通全流程：状态设计、转移方程、手工推演一遍

2.1 dp[i][j]到底表示什么

动态规划的第一步永远是定义状态。我见过很多人卡在“知道要用DP但不知道dp数组每个格子是什么意思”，其实只需要盯住一个原则：状态里必须包含决策需要的全部信息，并且这个信息要能从前面的状态递推过来。

对于01背包，经典的二维状态是dp[i][j]：只考虑前i株草药，且总耗时不超过j时，能获得的最大价值。注意i从1枚举到M，j从0枚举到T。为什么一定要加“前i株”这个限制？因为在考虑新增一株草药时，我们只需要知道“在不考虑这株草的情况下，各种剩余时间能带来的最大价值”，然后决定要不要把这株草塞进去，这天然形成了一种递推顺序。如果我们把状态定义成“任意i株草药”，那根本没法递推，因为你不知道之前选了哪些，信息就不完整。

初始化也非常简单：当i=0时，一株草药都没考虑，无论j是多少，最大价值都是0，所以dp[0][j]=0。二维数组初始化为全0即可，因为任何选不到草药的情况价值就是0，不像求最小值那类问题需要初始化成正无穷。这一点虽然简单，但很多入门选手会在后期做“恰好装满”变体时搞混，先在这里记下：P1048是“不超过容量”，初始化为0是对的。

2.2 转移方程的由来：取还是不取

转移方程是这道题的核心，写成代码只有一行，但为什么是这一行，很多人说不清。考虑第i株草药，它的采摘耗时是cost[i]，价值是value[i]。假设我们已经算出了dp[i-1][...]，现在要决定第i株草药怎么处理。

• 不取第i株：dp[i][j]直接等于dp[i-1][j]，意思是前i-1株已经在耗时j的约束下做到了最优，这一株跳过。
• 取第i株：前提是j >= cost[i]。如果取了，价值会增加value[i]，但剩余时间会减少cost[i]，所以这一分支的价值是dp[i-1][j - cost[i]] + value[i]。

两者取最大值，就得到转移方程：dp[i][j] = max(dp[i-1][j], dp[i-1][j - cost[i]] + value[i])第二个选项只在j >= cost[i]时可用。

这个方程的精妙之处在于，它把所有可能的中间状态压缩成了两种选择。你可能疑惑：不取的情况下dp[i-1][j]已经是最优，取了之后凭什么更优？因为之前的最优方案不包含第i株的价值，而dp[i-1][j - cost[i]]让出了一部分耗时给第i株。如果让出耗时之后，新组合的总价值更大，dp[i][j]就会更新；如果第i株又重又没价值，取它的分支就会被max自动筛掉。

我习惯把这个过程想成一个“拍板”场景：每来一株新草药，我手里都有一张表，表里记录了前i-1株情况下每个耗时上限对应的最大价值，然后对着这一株的耗时和价值，要么把它填进某个空当，要么直接放弃。这个过程不需要回溯重新排列之前的方案，因为之前的所有方案已经被dp[i-1][j]完整地记录了。

2.3 手推示例输入的完整过程

光说理论容易飘，我拿题目自带的示例走一遍。输入是：

70 3 71 100 69 1 1 2

总时间T=70，共3株草药。第1株耗时71、价值100；第2株耗时69、价值1；第3株耗时1、价值2。注意第1株耗时71大于总时间70，所以它在任何状态下都不可能被选。理论上的最优选择是第2株加第3株，总耗时69+1=70，总价值1+2=3，和样例输出3完全一致。

手动填dp表时，按i从1到3、j从0到70一层一层算。第1株cost=71，因为71比所有j都大，所以dp[1][j]整行都是0，等价于“这株采不了”。第2株cost=69、value=1，那么当j从0到68时dp[2][j]=0；当j=69时，max(dp[1][69], dp[1][0]+1)=max(0,1)=1；当j=70时，同理max(0, dp[1][1]+1)=1。第3株cost=1、value=2，当j>=1时，不取分支dp[2][j]和取分支dp[2][j-1]+2之间取最大值。到j=70时，不取分支是dp[2][70]=1，取分支是dp[2][69]+2=1+2=3，所以dp[3][70]=3，答案就是3。

这种题只要亲手推一次二维表，就会彻底摆脱“看着代码觉得对但不知道为什么对”的晕车感。我建议你拿到任何一道不熟的DP题，先在草稿纸上画一个小规模的表，跑完一遍再写代码，写代码时每一步都能对得上，出错概率会直线下降。

3. 一维滚动数组优化：为什么必须倒着枚举容量

3.1 空间优化的动机和做法

二维DP写完之后AC没有问题，但学完二维写法，很多人会再往前走一步：把二维数组压成一维数组。为什么有必要？因为实际竞赛中背包题往往不会只给1000的容量。当T去到10万、100万，dp[M+1][T+1]会瞬间涨到几百MB甚至几GB，内存直接爆掉。所以滚动数组不是炫技，是真实需求。

观察转移方程dp[i][j] = max(dp[i-1][j], dp[i-1][j-cost[i]] + value[i])，你会发现第i行只依赖第i-1行，跟更早的行完全没有关系。这意味着我们不需要保存全部M行历史记录，只需要保留“上一行”的结果，每次用上一行推出新一行，然后丢弃旧行。实现上就是只开一维数组dp[j]，外层循环i枚举每株草药，内层循环j枚举容量，不断刷新同一个dp数组。

核心代码长这样：

#include <bits/stdc++.h> using namespace std; int main() { int T, M; cin >> T >> M; vector<int> cost(M + 1), value(M + 1); for (int i = 1; i <= M; i++) { cin >> cost[i] >> value[i]; } vector<int> dp(T + 1, 0); for (int i = 1; i <= M; i++) { for (int j = T; j >= cost[i]; j--) { dp[j] = max(dp[j], dp[j - cost[i]] + value[i]); } } cout << dp[T] << endl; return 0; }

如果还不够熟悉，可以把双层循环理解成“一个物品一个物品地尝试装入背包”，每个物品都试图更新所有容量下的最优值。写熟练之后，这个双层循环会成为肌肉记忆，但前提是你真的理解它为什么长这样。

3.2 倒序循环的底层原因

这是整个背包问题里最容易出错、也最值得掰开揉碎讲的一个点：为什么内层循环必须从T往下递减到cost[i]，而不能从cost[i]递增到T？

问题出在“覆盖”上。一维数组每一轮循环同时扮演着“上一行dp[i-1]”和“当前行dp[i]”两个角色。按理说，dp[j]更新时需要读取的是上一轮的dp[j]和dp[j-cost[i]]，不应该被这一轮已经更新的值污染。如果j从小到大循环，dp[j-cost[i]]在j>=cost[i]时往往已经在本轮被更新过了，读到的就是“这一轮又加了一次第i株”之后的值。这样一来，第i株草药就可能被重复取用，01背包就变成了完全背包，答案会偏大。

我举个极端例子：T=6，只有1株药，耗时为3，价值为10。如果是正序循环：

for (int j = cost[i]; j <= T; j++) { dp[j] = max(dp[j], dp[j - cost[i]] + value[i]); }

开始时dp全0。j=3时，dp[3]=max(0, dp[0]+10)=10；j=6时，dp[6]=max(0, dp[3]+10)=20。一株耗时3的草药却被贡献了20的价值，这明显是“采了两次”才可能得到的结果，而正确的01背包答案应该是10。如果你拿T=5来试，因为5容不下两个耗时3的物品，正序循环反而看不出问题，这就是为什么很多人写了正序还能碰巧AC一些样例，但一旦数据构造得巧妙一点就会WA。

倒序循环完全没有这个问题：j从6到3，先算dp[6]=max(0, dp[3]+10)=10，再算dp[3]=max(0, dp[0]+10)=10。更新dp[3]时已经不会回头影响dp[6]的计算了。本质上，倒序保证了每个物品在考虑过程中最多被取一次：当我们在算较大的j时，较小的j仍然保留着上一轮的结果；之后更新小j也不会反过来改动大j。这正好对应了“01”的含义。

每次有人问我“为什么背包一维要倒序”，我都会说：你去把正序跑一遍，输出中间数组，看到那个重复取物品的数值，你就再也不会忘了。亲手踩过之后，比听十遍讲解都管用。

3.3 从二维到一维还能看到什么

二维写法里第二个维度的j从0枚举到T，每一个都独立赋值；一维写法里内层循环只从T枚举到cost[i]，小于cost[i]的j不需要更新，因为它们本来就不可能取第i株，保持原值就行，顺带还省掉了一部分循环。

这个优化虽然省不了多少时间，最多省一半，但它理顺了一个概念：dp[j]的语义是“在总耗时不超过j的情况下能获得的最大价值”，它不依赖物品编号。外层每处理完一株草药，dp数组就自动从“只考虑前i-1株的结果”升级为“考虑前i株的结果”，整个过程像流水线一样层层刷新。理解了这个，后面再看完全背包、多重背包的优化，才会有坐标感。

4. 易错点复盘与同类题迁移

4.1 几个几乎人人都踩过的坑

第一个坑：下标从0开始还是从1开始。这道题我习惯从1开始存，cost[i]、value[i]的下标和循环里的i对应，dp数组下标从0到T。如果非要从0开始存也不是不行，但下标offset一多，转移方程里就很容易把cost[i-1]写成cost[i]，或者把循环边界写错。我见过不少WA就是错在这种地方。为了不让无谓的细节干扰算法本身，直接统一从1开始最省心。

第二个坑：忘记判断j >= cost[i]。二维写法里，只有在j >= cost[i]时才需要考虑取第i株，否则dp[i][j]=dp[i-1][j]。有些初学者把max两个分支直接写出来，没有条件判断，结果j-cost[i]变成负数，访问dp数组越界。C++里越界不一定会立刻崩溃，但会读到垃圾值，导致答案完全不可预期。一维写法因为循环起点直接是cost[i]，天然规避了负数下标问题，但二维写法一定要记得加判断。

第三个坑：答案下标搞错。有人会把答案写成dp[M][T-1]或dp[M-1][T]，因为“最后一个下标”这个概念容易让人产生错觉。记住时间是0到T的闭区间，T本身就是一个合法容量上限，dp[M][T]才是答案。

第四个坑比较隐蔽：单个草药的耗时可能超过总时间T。样例里第1株耗时71大于T=70，这就要求转移方程能天然处理“这个物品塞不进任何容量”的情况。二维写法靠j>=cost[i]的条件判断挡住它；一维写法里内层循环根本不进入，dp值保持不变，也不会出错。

我把这些坑整理成了一张表，方便对照：

4.2 如果题目换了个壳，你还认识它吗

P1048是01背包的原型题，但它最大的价值在于“换壳识别能力”。我们来看几道常见的变体。

如果问“恰好装满背包的最大价值”，初始化就要区分对待：dp[0]=0，其余dp[j]设为负无穷，表示只有容量恰好为j时才可能有合法值，不能正好装到某个容量就视为非法。这类题常见于“凑零钱”“选套餐总价恰好等于X”的场景。如果问“有多少种方案凑出某个价值”，转移方程从max变成累加：dp[j] += dp[j-cost[i]]，同时要注意枚举顺序，避免重复计数。如果每株草药可以采无限次，模型就从01背包变成了完全背包，一维写法只需要把内层循环从倒序改成正序，其他什么都不用变。这个对照记忆非常有用：倒序等于每种最多一次，正序等于每种可以无限次。如果每种草药有数量限制，那就是多重背包，要上二进制拆分或单调队列优化。

我讲这些变体，不是为了让你一下子全学会，而是想强调：无论题目怎么包装，核心永远是“物品、容量、价值、选择次数”这四件事。把P1048吃透，就是把这四件事的建模方式吃透，后面遇到换壳题才不会懵。

4.3 关于代码风格和提交时的细节

最后说点提交层面的经验。P1048这题的数据设计得很经典，用朴素的cin/cout就能过，不需要刻意快读。不过养成快读的习惯也没坏处，后面很多背包题的输入量会很大。我个人的习惯是：

ios::sync_with_stdio(false); cin.tie(nullptr);

这两行加上之后，cin和cout的速度足够应付大部分单组输入题目。数组用vector还是静态数组都可以，这题数据范围小，开int dp[1005][1005]也很稳，反而免去了vector的resize环节，适合快速提交。

还有一个小细节：如果题目存在多组输入，记得每次循环都要清空dp数组。P1048是单组输入，所以不用考虑这个。但万一你之后改题遇到多组测试，清空逻辑漏掉的话，上一组的数据会污染下一组的答案，这类bug往往很难查。我的习惯是在读取T、M之后立刻初始化dp，把它和输入绑定在一起，而不是只想着全局数组初始一次就完事。

5. 这道题到底在训练什么：从“会做P1048”到“会做一类背包题”

很多人AC之后就把这题扔了，觉得“不过是一道简单的DP入门题”。但我觉得，P1048真正的价值在于帮你建立一套完整的背包建模思维，这个过程可以拆成四步：识别物品、识别容量、识别价值、确定选择次数。

第一步识别物品，对应题目里的“每株草药”，它携带两个属性：耗时（重量）和价值。第二步识别容量，对应“总时间T”，它是被分配的资源上限。第三步识别价值，对应“草药的价值”，它是我们要最大化的目标函数。第四步确定选择次数，题目里每株草药只能采一次，所以是01选择。如果原题说同一种草药可以采多株，模型就变了。这四步在任何背包题里都适用，区别只在于选择次数的限制不同。

我还想强调，01背包的DP之所以经典，是因为它第一次真正展示了“状态转移”的意义：你不需要枚举所有2的M次方种组合，只需要通过M乘T个状态，就能把问题压缩到多项式时间。这个过程本质上是在做信息合并，把大量子集枚举的结果合并成一张表，表里只保留每个耗时上限下的最优方案。当你理解了这种合并思想，以后再遇到状态压缩DP、区间DP、数位DP，都会觉得它们是在同一个思想框架下变戏法。

回到训练方法上，我建议的学习顺序是这样的：先用二维DP AC掉P1048，再改成滚动数组的一维DP，再照着模板写一遍完全背包，最后做一两道“恰好装满”或“方案数”的变体。这样一轮下来，你对背包问题的理解就不再是背代码，而是真正知道每一行代码为什么存在。我在给一个刚开始学算法的同学讲这道题的时候，他就是靠这个顺序，从完全不懂DP到能独立做出中等难度的分组背包，可见方法比埋头刷题重要得多。

我自己的经验是，无论后来刷了多少道题，P1048这种经典题值得每隔一段时间回来重写一遍。第一次写的时候，我只知道照抄模板；过了几个月再写，我开始懂倒序循环为什么对；再过一阵子写，我已经能在脑子里直接把二维表格演算出来。每一次重写都在验证你对动态规划理解的深度。如果你现在正卡在“看着题解会写，合上书就懵”的阶段，别急着刷下一题，回到这道采药题，从二维开始，亲手推一遍表，再改成一维，你的感觉会完全不一样。这道题的代码量不大，但它是一个极好的理解标尺。