【题目来源】
洛谷：P1048 [NOIP 2005 普及组] 采药 - 洛谷 (luogu.com.cn)
【题目描述】
辰辰是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。为此，他想拜附近最有威望的医师为师。医师为了判断他的资质，给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说：“孩子，这个山洞里有一些不同的草药，采每一株都需要一些时间，每一株也有它自身的价值。我会给你一段时间，在这段时间里，你可以采到一些草药。如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大。”
如果你是辰辰，你能完成这个任务吗？
【输入】
第一行有 \(2\) 个整数 \(T\)（\(1≤T≤1000\)）和 \(M\)（\(1≤M≤100\)），用一个空格隔开，\(T\) 代表总共能够用来采药的时间，\(M\) 代表山洞里的草药的数目。
接下来的 \(M\) 行每行包括两个在 \(1\) 到 \(100\) 之间（包括 \(1\) 和 \(100\)）的整数，分别表示采摘某株草药的时间和这株草药的价值。
【输出】
输出在规定的时间内可以采到的草药的最大总价值。
【输入样例】
70 3
71 100
69 1
1 2
【输出样例】
3
【算法标签】
《洛谷 P1048 采药》 动态规划,dp #背包# #NOIP普及组# #2005#
【代码详解】
#include <bits/stdc++.h> // 包含标准库头文件
using namespace std;const int M = 105, T = 1005; // 最大草药数量和最大采药时间// 动态规划数组：f[i][j]表示前i种草药在j时间内能获得的最大价值
int f[M][T]; // 每种草药的采集时间和价值
int tim[M], ve[M]; // 总采药时间和草药数量
int t, m; int main()
{// 输入总采药时间和草药数量cin >> t >> m;// 输入每种草药的采集时间和价值for (int i = 1; i <= m; i++) cin >> tim[i] >> ve[i];// 动态规划处理for (int i = 1; i <= m; i++) { // 遍历每种草药for (int j = 1; j <= t; j++) { // 遍历每个可能的时间点// 默认不选当前草药，继承前i-1种草药的最优解f[i][j] = f[i - 1][j];// 如果当前时间足够采集当前草药if (j >= tim[i]) {// 比较不选当前草药和选当前草药哪个更优// 选当前草药的价值 = 前i-1种草药在(j-tim[i])时间内的最优解 + 当前草药价值f[i][j] = max(f[i][j], f[i - 1][j - tim[i]] + ve[i]);}}}// 输出前m种草药在t时间内能获得的最大价值cout << f[m][t] << endl;return 0;
}
【运行结果】
70 3
71 100
69 1
1 2
3