P1048 采药这道题在算法题库里的地位差不多等于学DP必须翻过的一座小山。名字很朴素但内核就是最经典的DP模型之一01背包。当年我第一次AC它的时候还不太理解为什么内层循环要从大到小只知道照着模板抄。后来我才明白把这道题真正吃透你就掌握了背包类问题的通用钥匙。这个场景讲的是采药少年在有限时间里决定采哪几株草药但本质上和你去超市在预算内挑东西一模一样每件物品只能买一次怎么让总价值最高。这篇就来完整拆解P1048从题面建模到状态设计从二维写法到一维优化再到最容易踩的坑和它派生的背包变体。刚接触动态规划的人可以把它当作第一道入门题已经刷过很多题的人也可以回来对照一下自己的理解有没有出现偏差。1. 题目核心与背包模型识别1.1 题目到底在说什么先看题面。你有总时间T面前有M株草药。每株草药都告诉你两个数字需要花费的采集时间w_i以及它带来的价值v_i。你在整个采药过程中每株草药最多只能采一次。目标是让总花费时间不超过T的情况下采到的总价值尽量大输出最大的价值即可。注意“不超过T”意味着可以不把时间用满空出来的时间不会受到惩罚。我随便举一组数据T70三株草药分别{71,100}、{69,1}、{1,2}。看到第一株耗时71价值100听起来很诱人但它已经超出了总时间直接排除。剩下两株总耗时70正好卡满总价值3。如果你按“单位时间价值”来贪心第一株单位价值约1.41后两株分别约0.014和2贪心会选第三株和第一株但第一株装不下最终就会掉进坑里。所以这类组合问题不能用性价比排序直接解需要系统地搜索所有可能的组合而动态规划就是干这件事最成熟的手段。很多人一看到“最大价值”就以为能用贪心但实际上贪心只适用于物品可以切割的情况。采药和背包里装的物品一样是不可分割的整体要么整株采走要么一株不采。这种离散的选择天然就是组合优化问题。P1048故意把题面写得很短不给你任何干扰条件目的就是让你把注意力集中在“有限容量 一次取用 最大价值”这三个要素上。1.2 为什么一眼就要认定是01背包判断一个题是不是01背包就看三件事容量上限、物品清单、取用次数。这里容量上限是T物品清单是M每种物品取用次数为0或1这就是01。再加上求最大总价值特征非常明显。与之对比如果同一种草药可以无限采那就是完全背包如果限定了具体个数那就是多重背包。P1048故意把模型压得很纯净就是为了让入门的人一眼能辨认出最基础的形态。很多题不会直接说“背包”而是给你一个资源限制下做选择的场景比如时间、空间、体积、重量、预算。采药用时间是容量换成体积就是常见的装包问题。你只要能把实际场景里的“限制量”对应到背包容量把每个决策对应到物品的“成本”和“收益”模型识别就已经完成大半。这一步比写转移方程更重要模型认错后面再怎么优化都白搭。我见过有人把01背包当成贪心去做也有人把完全背包的模板套到01上都是因为模型识别没过关。1.3 数据范围与复杂度红线虽然P1048的数据范围不大但学算法一定要养成先看范围的直觉。假设M和T都在1000这个量级二维状态大概是1e6个int内存4MB左右非常安全如果T到了1e5二维的O(MT)虽然时间上可能还能接受但内存要400MB明显不行这时候就必须转成一维。所以在比赛或者刷题时看到M和T相乘接近1e7就要考虑空间优化超过1e8时间上也要谨慎。复杂度O(MT)是这个模型逃不掉的下限优化空间只能从空间入手不能改变状态总数。这里给新手一个经验值状态总数在1e6到1e7之间都是可以放心用二维数组的1e8以上千万别开二维一维倒序循环才是正解。P1048的常见范围也就是M和T两位数到三位数二维足够应付但我会在下一节直接带你走到一维因为那是所有背包题都绕不开的最终形态。2. 从暴力枚举到DP的思路演进2.1 枚举所有组合不行但能启发思路最简单粗暴的方法是把所有选法枚举一遍。考虑第1株的时候选或不选考虑第2株的时候再选或不选一直下去一共2^M种组合。M20时已经接近100万M30就能到10亿完全没法接受。可是枚举的过程给了我们一个重要发现后面的决策只依赖“已经考虑到了第几株”和“剩余时间还剩多少”并不关心之前具体选了哪些。这就出现了大量重叠的子问题也是动态规划能切入的根本原因。当你有重叠子问题最自然的写法是记忆化搜索。定义一个函数dfs(i, j)意思是前i株草药、剩余j时间时的最大价值。对于第i株要么不采直接去处理i-1要么在时间足够时采了之后处理i-1两者取最大值。写成递归再配一个二维数组存结果就能把复杂度从2^M降到O(M*T)。记忆化搜索和递推DP其实是一个东西区别只是实现方向不同。很多新手绕开记忆化直接学递推容易对状态转移的来源困惑所以这里值得点一句。2.2 状态定义从“选没选过”到“容量维度”正式的DP会用递推数组代替递归。定义dp[i][j]表示从前i株草药中选总耗时不超过j时能得到的最大价值。这里有两个重点。第一为什么要有i这个维度因为要告诉DP当前考虑到了哪一株决策过程有先后。第二为什么j定义成“不超过”而不是“恰好等于”如果定义成恰好等于j初始化会非常麻烦只有dp[0][0]0其他都要设成负无穷因为“恰好等于”的状态可能不存在。而定义成不超过j只要容量没用满就依然合法初始化全部为0即可转移时还能从dp[i-1][j]继承不选的情况。下标上我习惯让i从1开始dp[0][j]0表示一株都不考虑时任何容量下总价值都是0。数组大小必须开到T1因为j取值范围是0到T。很多人只开到T一访问dp[T]就数组越界这是个低级但频繁的错误。为什么状态维度的命名要这么讲究因为后续所有推导都建立在下标语义一致的基础上。如果用“剩余时间”作为第二维转移方程看起来是dp[i][rest]访问是dp[i-1][rest-w[i]]本质上一样只是写代码时容易混乱。我建议新手固定成“容量j”而不是“剩余时间”这样容量的边界、数组索引和转移条件三者一一对应调试时一眼能看出越界问题。2.3 转移方程的由来选还是不选转移方程其实就是在回答一个问题面对第i株草药我该怎么办答案只有两种。不采那当前状态直接继承dp[i-1][j]采那需要先保证时间够即j≥w_i然后把当前这株的价值v_i加到之前用j-w_i时间能得到的最大价值上也就是dp[i-1][j-w_i]v_i。取两者最大值就是dp[i][j]。写成公式是dp[i][j] max(dp[i-1][j], dp[i-1][j-w_i] v_i)当j≥w_i。如果没有足够时间就只能走不采分支。这里特别要注意采了第i株之后前面的状态用的是i-1而不是i。如果写成dp[i][j-w_i]v_i就变成了允许重复取同一株整个模型都变了。这个区别在理解一维优化时尤其关键因为你会看到一维循环里的dp[j-w[i]]必须来自上一轮。我一直觉得一个转移方程如果只是背下来那就只是一行符号。但如果你能对着它问出“为什么是max”“为什么是j-w_i”“为什么是i-1”你就真正掌握了它。采药这道题恰好把这三个问题都摆在了明面上答案也都很干净max是因为两种决策只能选一个j-w_i是扣掉当前物品消耗的时间i-1是保证当前物品不会被重复使用。3. 从二维DP到一维DP的优化落地3.1 二维数组实现先求对再求快第一版代码我建议老老实实开二维数组。这不是浪费时间而是让你能用眼睛观察每一行是怎么从上一行推出来的。看下面的C实现。#include bits/stdc.h using namespace std; const int MAXT 1005, MAXM 105; int w[MAXM], v[MAXM]; int dp[MAXM][MAXT]; int main() { int T, M; cin T M; for (int i 1; i M; i) { cin w[i] v[i]; } for (int i 1; i M; i) { for (int j 0; j T; j) { dp[i][j] dp[i-1][j]; // 不采第i株 if (j w[i]) { dp[i][j] max(dp[i][j], dp[i-1][j-w[i]] v[i]); } } } cout dp[M][T] endl; return 0; }这里先执行dp[i][j]dp[i-1][j]把不选的情况作为默认值然后再判断j≥w[i]时用max更新。如果不先赋值可能会拿到dp[i][j]里上一轮的残留值结果就会出错。内层for循环从0到T是为了把所有容量都填满这样下一行推导时所需的dp[i-1][j-w[i]]一定已经计算好。运行后输出dp[M][T]就是所有草药考虑完、容量为T时的最大价值。二维写法的好处是每一格都清清楚楚调试时可以打印整张表人工核对。比如前几行容量小、装不下东西时dp值应该都是0容量慢慢变大某些物品能够放进去了值才开始跳跃。我建议新手拿到样例数据后真的把这张表在纸上手推一遍比盯着屏幕空想有用得多。3.2 滚动数组省掉一维观察二维转移会发现dp[i][]只依赖dp[i-1][]和dp[i-2]、dp[i-3]这些更早的行没有关系。既然这样我们不需要保留整个二维表只要两行一行当“上一轮”一行当“当前轮”用完就交换。这就是滚动数组。#include bits/stdc.h using namespace std; const int MAXT 1005; int w[MAXM], v[MAXM]; int dp[2][MAXT]; int main() { int T, M; cin T M; for (int i 1; i M; i) { cin w[i] v[i]; } int cur 0, pre 1; for (int i 1; i M; i) { swap(cur, pre); for (int j 0; j T; j) { dp[cur][j] dp[pre][j]; if (j w[i]) { dp[cur][j] max(dp[cur][j], dp[pre][j-w[i]] v[i]); } } } cout dp[cur][T] endl; return 0; }滚动数组出现一个容易忽略的细节每次交换后dp[cur][j]里可能还有更早遗留的旧值所以要先执行dp[cur][j]dp[pre][j]把本轮默认值写进去再做max。如果偷懒不覆盖下一轮的j可能把上一轮残留的数值当作基础样例可能能过换个数据就随机出错这种bug最难查。我的经验是如果开着二维能过、改成滚动就不稳十有八九是初始化漏了。3.3 一维倒序循环为什么“倒序”是灵魂滚动数组其实还提示我们既然只需要一行能不能干脆用一个一维数组反复更新从理论上看完全可行但更新顺序必须从后往前。看这个核心代码。for (int i 1; i M; i) { for (int j T; j w[i]; j--) { dp[j] max(dp[j], dp[j - w[i]] v[i]); } }为什么必须倒序因为在原地更新时dp[j-w[i]]如果已经被当前第i株更新过那再用来更新dp[j]就等于同一株默认能采两次。倒序从T往w[i]走时j-w[i]一定比j小而更小的索引还没有被本轮更新所以它仍然保存着上一轮的值正好对应dp[i-1][j-w[i]]。说得更直白一点你在黑板上一排格子从左到右写新值倒序更新就像从右往左写左边还没动你可以放心参考。很多文章一上来就丢给你一维模板却没解释为什么倒序。我学的时候就是没搞懂这一点导致每次做背包题要么顺序写反要么完全背包和01背包混着用。后来我养成一个习惯拿到任何背包题先问“物品能不能重复取”。能重复取内层正序不能重复取内层倒序。这个判断比背模板快得多。4. 采药题全真排错与实战经验4.1 内层循环写成正序的惨案这是01背包里排名第一的错误把for (int jT; jw[i]; --j)写成for (int jw[i]; jT; j)。同样是采药正序会让问题变成完全背包也就是每一种草药可以被重复无限次采。用刚才那组样例第三株草药耗时1、价值2正序会反复采样1时间的草药最后凑出总耗时70价值140答案直接飞到天上。这时候只要检查循环方向几乎不用怀疑算法其他部分。另外还有一种写法是把两个维度循环顺序反过来比如先遍历容量再遍历物品也会出问题。01背包的更新必须保证物品维是外层容量维是内层因为状态转移依赖上一轮物品的完整容量表。如果先容量后物品就等于在同一个容量上反复叠加多个物品同样违背01语义。所以代码顺序和方向一样重要。我在带新手的时候遇到输出结果比正确答案大的情况第一反应永远是检查内层循环方向。这个bug概率极高而且非常好修但如果不养成条件反射可能会浪费很多时间在别的地方。遇到答案偏小的则多半是数组越界或者初始值设置错了。4.2 边界条件的两个陷阱第一个陷阱是数组大小。二维数组dp[M1][T1]中第二维下标最大取到T所以数组第二维长度至少是T1。用一维数组时也一样声明dp[T1]最安全。如果你开了dp[T]最后的dp[T]就是越界访问结果是未定义行为可能本地没问题换环境又崩掉。第二个陷阱是初始值。用“不超过j”的定义时dp数组全部初始化为0就是正确起点。但如果你把问题改成“恰好装满”就要初始化dp[0]0其他为负无穷否则你无法区分容量恰好用完和未达到容量的状态。P1048问最大价值不要求用完时间所以全0初始值很安全。做题时我会顺手特判一下T和M为0的情况虽然题目一般不会这样但一个稳妥的写法能减少很多无谓的越界或空循环问题。4.3 读取输入与数组大小的约定P1048的输入格式是第一行两个整数T和M表示总时间和草药株数接下来M行每行两个整数分别是采集时间和价值。一个常见的低级错误是把T和M读反导致容量数组越界或者循环次数错误。我在调试时发现输出特别离谱第一步就是检查cinTM是不是写成cinMT。顺手写一组自测数据T10, M2两株草药分别是(6,30)和(5,20)。容量10单独选第一个价值30选两个需要11超时所以答案应该是30。如果你输出了40或50说明背包逻辑出问题了。这种两三个物品的手工数据比任何调试器都好用因为它能激活大脑里的“人肉DP”。4.4 一维滚动实现的最终模板把上面的经验汇总我最常用的一维版本是这样。#include bits/stdc.h using namespace std; const int MAXT 1005; int dp[MAXT]; int main() { int T, M; cin T M; for (int i 0; i M; i) { int w, v; cin w v; for (int j T; j w; j--) { dp[j] max(dp[j], dp[j - w] v); } } cout dp[T] endl; return 0; }这段代码边读边处理不需要保存w和v数组因为每一株草药都是一次性更新。外层for每读入一组数据就做一次01背包更新内层for用倒序。输出的dp[T]就是答案。这个模板很短但前提是你已经理解它背后的二维语义如果只是背下来遇到完全背包、多重背包还是会懵。所以我建议平常练习时先在草稿纸上把二维表手推三五行再对照一维模板敲一遍。5. 从采药出发背包模型的变体和真实应用5.1 完全背包换一种遍历方向把P1048改一个条件如果每株草药都能无限重复采就变成了完全背包。这时内层循环改成从w[i]到T正向遍历。为什么正序就对了因为正序允许dp[j-w[i]]已经被当前物品更新过本质上支持了当前物品被多次累加而这正是“无限取”的含义。完全背包的经典例子是找零钱给定无限枚硬币凑成某个金额有多少种方案。核心代码差别仅仅是一行循环方向这恰好说明弄懂倒序原理多么重要。我在讲解的时候经常用一个比喻倒序循环像排队打饭每个人只打一次队伍从后往前叫号前面的人不会被重复叫到正序循环像自助餐可以反复取同一个菜每次取完还能再去取。虽然比喻不严格但对初学者建立直觉非常有帮助。5.2 多重背包二进制拆分思路如果题目给的是每种草药最多能采c[i]次那就是多重背包。最朴素的办法是把c[i]个同样的物品拆开变成c[i]个只能取一次的01物品但这样做物品总量可能爆炸。更优雅的是二进制拆分把c[i]拆成1、2、4、8……直到剩下的数字小于2的幂比如10拆成1、2、4、3。任意1到10之间的数量都能由这些组里的若干组拼出来。拆完后每组作为一个新物品跑一遍01背包即可。多重背包的模型在现实中很常见比如每种材料有库存量每件产品需要消耗固定材料、产生固定收益。P1048作为01入门题虽然不考多重背包但它给你打下的是“物品次数”这个变量的敏感度次数是0/1、无限、还是有限直接决定用哪种模板。5.3 项目调度中的01背包离题但不离型抛开刷题01背包在真实生活里也有很直观的投射。比如你只有30天空闲想在这个周期里学几门技能课程每门课需要投入的时间不同对职业发展的“价值”也不同你不可能把每门课都学完每个课程最多安排一次这就成了典型的01背包容量是30天每门课是物品求价值最大的选课组合。又比如一个项目排期里加班时间是有限的每个需求包需要不同的工时、带来不同的业务价值也可能有依赖关系这时01背包可以作为最基础的模型后面再加上依赖关系、并发约束等。现实中不会有人直接告诉你“这是01背包”但你能把场景里的限制量和收益量抽出来就已经值回票价。这也是我为什么一直觉得P1048这种基础题不能只当作刷题量的一部分更应该当成一种思维训练识别模型、设计状态、验证转移。最后说点个人感受。我学DP的时候P1048是个绕不开的坎但那时候总想快点背模板去刷更多题。后来带过一些新手发现凡是能把这道题二维写清楚、把倒序讲明白的人后面遇到完全背包、多重背包、分组背包都会非常顺。反过来一上来就抄一维代码的经常会在某个稍复杂的变体上折戟。所以我的建议很简单先在纸上把二维表画一遍再用滚动数组过渡到一维最后把“倒序”两个字刻进DNA。到了这一步采药这道题才算真的被你吞下。