P1048 [NOIP 2005 普及组] 采药 题解复盘模块动态规划类型01背包目标在有限时间内选择若干草药使总价值最大基本信息项目内容题目编号、来源P1048 NOIP 2005 普及组训练层级普及知识版块01背包、一维DP、状态转移解题前・关键信号识别维度分析目标、约束、底层结构在规定时间 T 内采摘草药使价值最大。每株草药只能采一次因此每个物品只有选和不选两种状态。底层结构为 01 背包。数据规模T≤1000M≤100可以使用 O(MT) 的动态规划。候选算法和依据暴力枚举每株草药选不选复杂度 O(2^M)无法通过。使用动态规划将问题转化为 01 背包。复杂度预判时间复杂度O(M×T)空间复杂度O(T)解题后・外化复盘维度内容状态定义定义dp[j]表示在当前已经考虑的草药中使用时间不超过 j 时能够获得的最大价值。状态转移对于第 i 株草药不选择dp[j]选择dp[j-t[i]]v[i]转移方程dp[j]max(dp[j],dp[j-t[i]]v[i])遍历顺序01背包必须倒序遍历容量for(jT;jt[i];j--)原因防止同一个物品被重复选择。实现结构 / 核心思路1. 枚举每一株草药。2. 使用一维数组 dp 保存当前时间限制下的最大价值。3. 对时间倒序更新保证每株草药只使用一次。错因回溯容易错误地将循环写成正序导致一个物品被重复使用变成完全背包。边界和易错点1. 01背包容量必须倒序。2. 答案为dp[T]。3. dp 初始化为 0 即可。下次看到什么信号我应该想到这个方法看到① 有容量限制② 每个物品只能选择一次③ 求最大价值想到01背包容量倒序。AC完整代码#includeiostream#includealgorithmusingnamespacestd;intmain(){intT,M;cinTM;intt[1005],v[1005];intdp[1005]{0};for(inti1;iM;i){cint[i]v[i];}for(inti1;iM;i){for(intjT;jt[i];j--){dp[j]max(dp[j],dp[j-t[i]]v[i]);}}coutdp[T];return0;}P1616 疯狂的采药 题解复盘模块动态规划类型完全背包目标在有限时间内无限次选择草药使价值最大基本信息项目内容题目编号、来源P1616 洛谷原创训练层级普及知识版块完全背包、一维DP、状态转移解题前・关键信号识别维度分析目标、约束、底层结构在规定时间内获得最大价值。每种草药可以无限采摘因此同一个物品可以重复选择。底层结构为完全背包。数据规模m≤10000t≤10^7且 m×t≤10^7。需要使用一维DP。候选算法和依据因为物品可以无限选择所以不能使用01背包。使用完全背包模型。复杂度预判时间复杂度O(M×T)空间复杂度O(T)解题后・外化复盘维度内容状态定义定义dp[j]表示在时间不超过 j 的情况下可以获得的最大价值。状态转移对于第 i 种草药不选择dp[j]选择一次dp[j-a[i]]b[i]转移方程dp[j]max(dp[j],dp[j-a[i]]b[i])遍历顺序完全背包需要正序遍历容量for(ja[i];jt;j)原因允许当前物品更新后的状态继续参与转移实现重复选择。实现结构 / 核心思路1. 枚举每种草药。2. 使用一维 dp 保存时间限制下的最大价值。3. 容量正序更新使同一种草药可以被多次使用。错因回溯1. 容易将循环写成倒序导致完全背包变成01背包。2. 最大价值可能超过 int 范围需要使用 long long。边界和易错点1. 完全背包容量必须正序。2. dp 数组使用 long long。3. 注意时间范围 t 最大为 10^7。下次看到什么信号我应该想到这个方法看到① 有容量限制② 物品可以无限选择③ 求最大价值想到完全背包容量正序。AC完整代码#includeiostream#includealgorithmusingnamespacestd;inta[10005];intb[10005];longlongdp[10000005];intmain(){intt,m;cintm;for(inti1;im;i){cina[i]b[i];}for(inti1;im;i){for(intja[i];jt;j){dp[j]max(dp[j],dp[j-a[i]]b[i]);}}coutdp[t];return0;}