🌿 采药人辰辰

📘 题目描述

辰辰是个天资聪颖的孩子，他梦想成为世界上最伟大的医师。

一天，他拜访了一位德高望重的医师。为了考验辰辰的资质，医师将他带到一个山洞中说：

“这里有很多珍贵的草药，每一株采摘需要一定时间，同时具有一定的药用价值。你只有一段时间，能否采到价值最大的草药，就看你的智慧了。”

如果你是辰辰，你能完成这个任务吗？

📥 输入格式

第一行输入两个整数 T 和 M：

• T：采药总时间（1 ≤ T ≤ 1000）
• M：草药种类数量（1 ≤ M ≤ 100）

接下来 M 行，每行两个整数 ti 和 vi：

• ti 表示采摘第 i 株草药所需时间（1 ≤ ti ≤ 100）
• vi 表示第 i 株草药的价值（1 ≤ vi ≤ 100）

📤 输出格式

输出在限定时间内能采到的最大草药总价值。

📌 输入样例

70 3
71 100
69 1
1 2

📌 输出样例

3

🧠 解题思路

这是一个 ​经典 0-1 背包问题​，每一株草药只能采一次。

• 状态定义：dp[j] 表示在时间为 j 时所能获得的最大价值。
• 转移方程：

  dp[j] = max(dp[j], dp[j - ti] + vi)   if j >= ti
  

• 初始化：dp[0] = 0，其他初始化为 0。