AcWing 423 采药：01背包问题从入门到精通

1. 从“采药”这道题说起它到底在考什么“AcWing 423 采药”这个标题放在算法练习的语境里其实是一道非常经典的01背包问题变形题。题目背景大致是一个采药人进山采药给定总时间 T有若干株草药每株草药有采摘所需时间和对应的价值每株草药只能采一次问在限定时间内能获得的最大总价值。如果你之前接触过动态规划看到这个描述应该会立刻反应过来——这不就是背包容量为 T、物品重量为时间、物品价值为草药价值的 01 背包吗但我想说的是这道题之所以被反复拿出来讲不是因为它难而是因为它足够典型。它几乎涵盖了 01 背包的所有核心要素状态定义、状态转移、空间优化、边界处理。很多人学动态规划卡在入门就是因为一上来就去看那些花里胡哨的区间 DP、树形 DP结果连最基础的“选或不选”都没吃透。而“采药”这道题恰好是帮你把“选或不选”这个最朴素的决策逻辑刻进肌肉记忆里的最佳素材。这篇文章我会从零开始把这道题拆到骨头缝里。不管你是刚学动态规划的新手还是已经刷过几道背包题但总觉得理解不够透彻的老手我都建议你跟着我的思路重新走一遍。因为我在实际教学和做题的过程中发现很多人对 01 背包的理解停留在“背模板”层面一旦题目换个马甲就懵了。而真正吃透“采药”这道题的人后面遇到“装箱问题”“数字组合”“目标和”这类变形题基本都能一眼看穿本质。先明确一下这篇文章适合谁看如果你连二维数组的 DP 都没写过那也没关系我会从最基础的状态定义讲起如果你已经能默写 01 背包的一维优化版本那你可以重点看我对边界条件、初始化细节和常见坑点的分析这些才是我踩过坑之后总结出来的真正有价值的东西。2. 01背包问题的核心思路拆解2.1 为什么“采药”本质上就是一个01背包我们先抛开题目包装把“采药”抽象成数学模型。假设总时间为 T有 n 株草药第 i 株草药需要花费 t[i] 的时间价值为 v[i]。每株草药你只有两种选择采或者不采。采的话消耗时间、获得价值不采的话什么都不发生。目标是在总时间不超过 T 的前提下让总价值最大。这个结构和 01 背包完全一致背包容量对应总时间 T物品重量对应采摘时间 t[i]物品价值对应草药价值 v[i]每个物品只能选一次。所以“采药”就是 01 背包问题的一个具体应用场景。题目换了背景但数学本质没有任何变化。我之所以强调这一点是因为很多初学者在做题时习惯按题目背景去记忆解法比如“采药就是用时间做容量”“装箱问题就是用箱子体积做容量”这样记当然也能做对题但一旦遇到新的背景就反应不过来。正确的做法是先识别问题的数学结构再套用对应的算法模型。识别结构的能力比记住十道题的解法更重要。2.2 状态定义dp数组到底表示什么01 背包最核心的一步就是定义状态。对于“采药”这道题我们定义dp[i][j] 表示从前 i 株草药中选择在总时间不超过 j 的前提下能获得的最大总价值。这个定义里有几个关键点需要说清楚。第一“从前 i 株中选择”意味着我们是在逐步扩大考虑范围先看前 1 株再看前 2 株一直到前 n 株。第二“总时间不超过 j”是一个约束条件注意是“不超过”而不是“恰好等于”这个区别在初始化的时候会影响结果。第三dp 数组存的是“最大总价值”也就是我们要求的最优解。为什么这么定义因为动态规划的核心思想就是把大问题拆成小问题并且小问题的最优解可以推导出大问题的最优解。当我们考虑前 i 株草药时对于第 i 株我们只有两种决策采或者不采。如果知道了前 i-1 株在各自时间限制下的最优解那么前 i 株的最优解就可以由这些子问题推出来。这就是状态定义的合理性所在。2.3 状态转移方程选与不选的博弈状态转移方程是动态规划的灵魂。对于“采药”这道题转移逻辑非常清晰如果不采第 i 株草药那么 dp[i][j] dp[i-1][j]因为总时间限制没变可选的草药少了一株最优解自然继承前 i-1 株的结果。如果采第 i 株草药那么前提是 j t[i]也就是当前时间限制足够采摘这株草药。采了之后剩余时间为 j - t[i]我们需要知道前 i-1 株在剩余时间下的最优解即 dp[i-1][j - t[i]]再加上第 i 株的价值 v[i]。所以完整的状态转移方程是dp[i][j] max(dp[i-1][j], dp[i-1][j - t[i]] v[i]) (当 j t[i]) dp[i][j] dp[i-1][j] (当 j t[i])这个方程看起来简单但里面有一个非常容易出错的细节当 j t[i] 时不能采第 i 株所以只能继承 dp[i-1][j]。很多人在写代码时会忘记这个条件判断直接写 max 表达式结果数组越界或者逻辑错误。我个人的经验是在写转移方程之前先把“不采”和“采”两种情况分别在纸上写清楚确认边界条件后再动手写代码。这个习惯帮我避免了无数次调试。2.4 二维到一维空间优化的原理与陷阱二维 DP 的时间复杂度是 O(nT)空间复杂度也是 O(nT)。对于“采药”这道题n 和 T 的范围通常不会太大二维数组完全够用。但如果 n 和 T 都达到几千甚至上万二维数组就可能超出内存限制。这时候就需要做空间优化把二维压缩成一维。空间优化的原理是dp[i][j] 只依赖于 dp[i-1][j] 和 dp[i-1][j - t[i]]也就是只依赖于上一行的数据。所以我们可以用一个一维数组 dp[j] 来滚动更新从后往前遍历 j保证在计算 dp[j] 时dp[j - t[i]] 还是上一轮即 i-1 轮的值。这里有一个极其关键的细节一维优化时内层循环必须从大到小遍历。如果从小到大遍历dp[j - t[i]] 可能已经被本轮更新过了那就相当于第 i 株草药被选了多次变成了完全背包问题。这个坑我见过太多人踩包括我自己早期学的时候也犯过这个错误。一维版本的转移方程for i in range(1, n1): for j in range(T, t[i]-1, -1): dp[j] max(dp[j], dp[j - t[i]] v[i])注意内层循环的起点是 T终点是 t[i]步长是 -1。这个循环顺序是 01 背包一维优化的标志性写法必须记牢。3. 完整实操过程与代码实现3.1 输入输出格式与数据范围分析在动手写代码之前我们先明确一下“采药”这道题的输入输出格式。通常这类题目的输入是这样的第一行两个整数 T 和 n分别表示总时间和草药数量。接下来 n 行每行两个整数 t[i] 和 v[i]分别表示第 i 株草药的采摘时间和价值。输出一个整数表示在总时间 T 内能获得的最大总价值。数据范围方面不同版本的题目可能有所不同但常见的范围是 T 1000n 100t[i] 和 v[i] 都是正整数。这个范围下二维 DP 和一维 DP 都能轻松通过。但如果 T 达到 10000 甚至更大就需要考虑一维优化了。我在实际做题时养成了一个习惯先看数据范围再决定用哪种实现方式。如果空间足够二维写法更直观、更不容易出错如果空间紧张再改成一维。不要一上来就追求最优写法先把问题做对再考虑优化。3.2 二维DP版本的完整代码与注释下面是我常用的二维 DP 写法用 Python 实现def solve(): T, n map(int, input().split()) t [0] * (n 1) v [0] * (n 1) for i in range(1, n 1): t[i], v[i] map(int, input().split()) # dp[i][j] 表示前 i 株草药时间不超过 j 的最大价值 dp [[0] * (T 1) for _ in range(n 1)] for i in range(1, n 1): for j in range(T 1): if j t[i]: dp[i][j] max(dp[i-1][j], dp[i-1][j - t[i]] v[i]) else: dp[i][j] dp[i-1][j] print(dp[n][T]) solve()这段代码的逻辑非常直白外层循环遍历每株草药内层循环遍历所有可能的时间限制。对于每个状态根据当前时间是否足够采摘第 i 株草药分别处理。有一个细节值得注意dp 数组的大小是 (n1) x (T1)多出来的一行和一列用于处理边界情况。dp[0][j] 表示不选任何草药时的最大价值显然都是 0。dp[i][0] 表示时间限制为 0 时的最大价值也都是 0。这些边界值在初始化时已经默认是 0不需要额外处理。3.3 一维DP版本的实现与对比一维版本的代码如下def solve(): T, n map(int, input().split()) t [0] * (n 1) v [0] * (n 1) for i in range(1, n 1): t[i], v[i] map(int, input().split()) dp [0] * (T 1) for i in range(1, n 1): for j in range(T, t[i] - 1, -1): dp[j] max(dp[j], dp[j - t[i]] v[i]) print(dp[T]) solve()对比两个版本一维版本少了一个维度代码更简洁空间复杂度从 O(nT) 降到了 O(T)。但代价是可读性稍微降低尤其是内层循环倒序遍历这个点如果不理解原理很容易写错。我个人的建议是初学阶段先用二维版本把原理吃透等完全理解了状态转移的过程再过渡到一维版本。不要一上来就背一维模板那样遇到变形题很容易翻车。3.4 手动模拟用小规模数据验证代码正确性为了确保代码逻辑正确我习惯用一组小规模数据手动模拟一遍。假设 T 10n 3三株草药分别是草药编号采摘时间价值15102463612手动模拟二维 DP 的过程考虑前 1 株dp[1][j] 在 j 5 时为 10否则为 0。考虑前 2 株dp[2][j] 在 j 9 时可以考虑两株都采价值 16在 j 5 时可以采第 1 株价值 10在 j 4 时可以采第 2 株价值 6。考虑前 3 株dp[3][10] 可以采第 1 和第 3 株时间 5611 超过 10不行可以采第 2 和第 3 株时间 4610价值 61218所以最优解是 18。用代码跑一遍输出确实是 18。这种手动模拟虽然费时间但对于理解 DP 的递推过程非常有帮助尤其是初学者强烈建议至少手动模拟两三组数据。4. 常见问题与排查技巧实录4.1 内层循环方向写反导致答案偏大这是 01 背包一维优化中最经典的错误。如果你把内层循环写成从小到大遍历那么对于每株草药dp[j - t[i]] 可能在当前轮已经被更新过了相当于同一株草药被重复采摘。结果就是答案偏大而且往往大得离谱。排查方法很简单用一组数据分别跑正序和倒序对比结果。如果正序结果更大那基本可以确定是循环方向问题。记住一句话01 背包倒序完全背包正序。这个口诀能帮你省下大量调试时间。4.2 数组越界与边界条件遗漏二维版本中如果忘记判断 j t[i]直接访问 dp[i-1][j - t[i]]当 j t[i] 时就会出现负数索引。在 Python 中负数索引不会报错但会取到数组末尾的值导致逻辑错误且难以发现。在 C 中则可能直接越界访问结果不可预测。我的做法是在写转移方程时先把 if-else 分支写完整确认所有边界都覆盖到了再考虑能不能合并成一行。不要为了代码简洁而牺牲正确性。4.3 初始化细节什么时候需要特殊处理标准的 01 背包问题中dp 数组全部初始化为 0 即可。因为 dp[i][j] 表示“时间不超过 j”的最大价值不选任何草药时价值为 0这是合法的。但如果题目要求“恰好用完时间 T”那初始化就需要调整dp[0] 0其余 dp[j] -infinity。这样只有恰好能装满的方案才会被选中。这个区别在“采药”这道题中通常不涉及但你在做其他背包变形题时一定要注意审题。4.4 常见问题速查表问题现象可能原因排查方法解决方案答案偏大一维循环方向写反对比正序和倒序结果内层循环改为倒序答案偏小初始化值设置不当检查 dp 数组初始值根据题意调整初始化运行时报错数组越界检查索引范围添加边界判断结果不稳定输入读取格式错误打印输入数据检查输入解析逻辑部分测试点超时时间复杂度太高分析算法复杂度使用一维优化或换算法4.5 我踩过的坑与实操心得第一个坑是过度依赖模板。我早期学背包的时候把一维模板背得滚瓜烂熟结果遇到一道题要求输出具体选了哪些草药我直接懵了。因为一维数组丢失了中间状态无法回溯方案。后来我才明白如果需要记录方案要么用二维数组要么额外开一个数组记录决策路径。第二个坑是忽略数据范围。有一次我做一道类似的背包题看都没看数据范围就直接写了一维 DP结果 T 达到 10^9一维数组根本开不下。后来才发现那道题需要用完全不同的思路比如贪心或者数学方法。所以做题前一定要先看数据范围这决定了你能用什么算法。第三个坑是不验证边界情况。比如 n 0 或者 T 0 的情况很多人在写代码时默认这些情况不会出现结果测试数据里偏偏有。我的习惯是在代码里加上对 n 0 和 T 0 的处理虽然多写几行但能避免不必要的失分。5. 从“采药”延伸到背包问题的变形与扩展5.1 完全背包每株草药可以采无限次如果把“采药”的条件改一下每株草药可以重复采摘那就变成了完全背包问题。状态转移方程变为dp[i][j] max(dp[i-1][j], dp[i][j - t[i]] v[i])注意这里变成了 dp[i][j - t[i]] 而不是 dp[i-1][j - t[i]]因为同一株草药可以多次选择。一维优化时内层循环改为正序遍历即可。这个变形在实际问题中很常见比如“零钱兑换”“资源分配”等场景。理解了 01 背包完全背包只需要改一个下标和一个循环方向。5.2 多重背包每株草药有数量限制如果每株草药最多采 k 次那就是多重背包问题。最朴素的解法是把每株草药拆成 k 个独立的物品然后跑 01 背包。但这样时间复杂度会很高。更高效的解法是二进制拆分或者单调队列优化。二进制拆分的思路是把 k 拆成 1, 2, 4, 8, ... 的组合这样可以用更少的物品数量表示所有可能的选取次数。比如 k 13可以拆成 1, 2, 4, 6 四组通过组合这四组可以表示 0 到 13 之间的任何数量。5.3 分组背包草药分成若干组每组只能选一株如果草药被分成若干组每组最多选一株那就是分组背包问题。解法是对每组内部做一次 01 背包组与组之间再合并。状态转移时外层循环遍历组内层循环遍历时间最内层遍历组内物品。这类问题在实际中对应“互斥选择”的场景比如选课时同一时间段只能选一门课。5.4 背包问题的识别技巧与实战建议我在做了几十道背包变形题之后总结出一个识别技巧看决策维度。如果每个物品只有选或不选两种状态就是 01 背包如果可以选多次就是完全背包如果有数量上限就是多重背包如果物品分组且组内互斥就是分组背包。识别出模型之后再根据数据范围选择合适的实现方式。小范围用二维大范围用一维超大范围考虑贪心或数学优化。这套方法论帮我在比赛中快速定位解法节省了大量思考时间。6. 动态规划思维的迁移应用“采药”这道题教会我们的不仅仅是一个背包模板更是一种用动态规划解决问题的思维方式。这种思维方式的核心是把大问题拆成子问题找到子问题之间的递推关系然后自底向上求解。这种思维可以迁移到很多其他场景。比如资源分配问题你有一定的预算要分配给若干个项目每个项目有成本和收益问如何分配收益最大。这本质上就是 01 背包。再比如时间管理问题你有一天的空闲时间有若干任务每个任务需要花费时间和精力问如何选择任务让产出最大。这也是 01 背包。我在实际工作中遇到过很多看似和算法无关的问题但仔细分析后发现都可以用背包模型来建模。比如服务器资源分配、广告投放预算分配、甚至个人学习时间分配。掌握背包问题不仅仅是多会做一道题而是多了一个分析问题的视角。最后分享一个我个人的学习习惯每学完一个算法我都会尝试把它套用到三个不同的实际场景中强迫自己完成从“抽象模型”到“具体应用”的转换。这个习惯让我对算法的理解不再停留在纸面上而是真正变成了可以随时调用的思维工具。对于“采药”这道题我套用的三个场景分别是预算分配、任务选择和资源调度。你不妨也试试看看能不能找到更多有趣的对应关系。