文字教学

这是一道经典的01背包问题，核心是每个草药只有选或不选两种选择，用动态规划记录最优解。

1. 状态定义：设 dp[j] 表示用 j 时间能采到的最大总价值。
2. 状态转移：对于每个草药（时间 t，价值 v），从后往前遍历时间 j（避免重复选同一个草药）：
   • 不选这个草药：dp[j] 保持不变。
   • 选这个草药：dp[j] = max(dp[j], dp[j - t] + v)（前提是 j >= t）。
3. 初始状态：dp 数组初始化为0，表示0时间时价值为0。
4. 最终答案：dp[T] 就是规定时间内的最大总价值。

代码

#include <bits/stdc++.h>
using namespace std;

int dp[1005];
int t[105], v[105];

int main() {
    int T, M;
    cin >> T >> M;
    for (int i = 1; i <= M; ++i) {
        cin >> t[i] >> v[i];
    }
    memset(dp, 0, sizeof(dp));
    for (int i = 1; i <= M; ++i) {
        for (int j = T; j >= t[i]; --j) {
            dp[j] = max(dp[j], dp[j - t[i]] + v[i]);
        }
    }
    cout << dp[T] << endl;
    return 0;
}