《采药》完整详细题解

一、题目分析

1. 题意转化为经典背包模型

• 总采药时间 T → 背包最大容量
• 草药数量 M → 物品个数
• 每株草药采摘耗时 w[i] → 物品重量
• 每株草药价值 v[i] → 物品价值
• 限制：每株草药只能采一次（01背包，每件物品只能选/不选二选一）
• 目标：总耗时不超过 T，采到草药总价值最大

2. 输入输出样例拆解

输入：

70 3
71 100  //草药1：耗时71，价值100（超过总时间70，完全不能采）
69 1    //草药2：耗时69，价值1
1 2     //草药3：耗时1，价值2

可选组合：草药2+草药3，总耗时 69+1=70，总价值 1+2=3，对应输出3。

二、动态规划核心思路（二维DP）

1. 状态定义

int dp[105][1005];

dp[i][j]：只考虑前i株草药，总采摘时间不超过j时，能获得的最大总价值

• 第一维i：草药编号（0~M，i=0代表一株草药都不选）
• 第二维j：可用总时间（0~T，j=0代表没有时间，价值必为0）

2. 初始化规则

全局数组默认初始值全为0，天然满足边界条件：

1. dp[0][j] = 0：一株草药都不采，无论多少时间，价值都是0
2. dp[i][0] = 0：没有任何可用时间，什么草药都采不了，价值0

3. 状态转移方程（核心）

遍历每一株草药i，再遍历所有可用时间j，分两种情况：

情况1：当前草药耗时 > 当前可用时间（w[i] > j）

时间不够，不能采第i株草药，最优解和只考虑前i-1株完全一样：

$$dp[i][j] = dp[i-1][j]$$

情况2：当前草药耗时 ≤ 当前可用时间（w[i] ≤ j）

有两种选择，取价值更大的一种：

1. 不采第i株：价值 = dp[i-1][j]
2. 采第i株：先预留出采它的时间w[i]，剩下j-w[i]时间在前i-1株里选最优，再加上当前草药价值：dp[i-1][j-w[i]] + v[i]

$$dp[i][j] = \max(dp[i-1][j], dp[i-1][j-w[i]]+v[i])$$

4. 最终答案

dp[M][T]：全部M株草药都考虑，总时间上限T，最大价值。

三、逐行代码详解

#include <bits/stdc++.h> //万能头文件，包含所有算法、输入输出头文件
using namespace std;

int t, m;                 //t总时间，m草药数量
int w[105], v[105];       //w[i]第i株草药耗时，v[i]第i株草药价值
int dp[105][1005];        //DP数组，dp[i][j]含义见上文

int main () {
    cin >> t >> m;       //读取总时间、草药数量
    //读入每一株草药的耗时和价值，下标从1开始（方便DP转移）
    for (int i = 1;i <= m;i++) {
        cin >> w[i] >> v[i];
    }

    //外层循环：依次处理前1、前2...前m株草药
    for (int i = 1;i <= m;i++) { 
        //内层循环：遍历0~t所有可用时间
        for (int j = 1;j <= t;j++) { 
            if (w[i] > j) {
                //时间不够，不能采当前草药，继承上一层结果
                dp[i][j] = dp[i - 1][j];
            } else {
                //能采，选“采/不采”中价值更大的方案
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i]);
            }
        }
    }
    //输出全部草药、总时间t下的最大价值
    cout << dp[m][t];
    return 0;
}

四、样例模拟推演（直观理解DP表格）

样例参数：t=70，m=3
草药1：w=71,v=100；草药2：w=69,v=1；草药3：w=1,v=2

1. i=1（处理第一株，耗时71）
   所有j≤70都满足71>j，所以整行dp[1][j] = dp[0][j] = 0，第一行全0。

2. i=2（处理第二株，耗时69，价值1）

   • j < 69：时间不足，dp[2][j]=0
   • j ≥ 69：可以采草药2，dp[2][j] = max(0, dp[1][j-69]+1) = 1
     即j=69~70时，值为1。

3. i=3（处理第三株，耗时1，价值2）
   逐个j计算，重点看j=70：

   • 不采草药3：dp[2][70]=1
   • 采草药3：dp[2][70-1] + 2 = dp[2][69] + 2 = 1 + 2 = 3
     取最大值3，最终dp[3][70]=3，和样例输出一致。

五、复杂度分析

• 时间复杂度：$O(M \times T)$
  外层循环M次，内层循环T次，本题M≤100，T≤1000，总运算量仅1e5，完全无压力。
• 空间复杂度：$O(M \times T)$
  二维数组105×1005，空间开销很小；进阶可使用一维滚动数组优化到$O(T)$。

六、易错点总结

1. 草药下标从1开始：避免j-w[i]出现负数，简化边界判断；
2. 内层循环j从小到大：二维DP无需倒序；一维01背包才需要倒序遍历容量；
3. 区分01背包和完全背包：本题每株草药只能采一次，不能重复选取；
4. 不要输出dp[m][t]以外的值，必须同时包含全部草药和全部可用时间。

七、拓展：一维空间优化版（可选拓展）

二维数组会重复使用上一层数据，可以压缩成一维数组，只用dp[j]：

#include <bits/stdc++.h>
using namespace std;
int t,m,w[105],v[105],dp[1005];
int main(){
    cin>>t>>m;
    for(int i=1;i<=m;i++) cin>>w[i]>>v[i];
    for(int i=1;i<=m;i++){
        //一维01背包容量必须倒序，防止重复选取
        for(int j=t;j>=w[i];j--){
            dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
        }
    }
    cout<<dp[t];
    return 0;
}