本文共 812 字，大约阅读时间需要 2 分钟。

为了解决这个问题，我们需要使用动态规划来解决一个典型的0-1背包问题。我们需要在给定的时间内选择草药，使其总价值最大化。

方法思路

解决代码

#include 
   
    using namespace std;int main() {    int T, M;    // 读取输入    cin >> T >> M;    // 一维数组初始化    int dp[T + 1] = {0};    for (int i = 0; i < M; ++i) {        int a, b;        cin >> a >> b;        for (int j = T; j >= a; --j) {            dp[j] = max(dp[j], dp[j - a] + b);        }    }    cout << dp[T] << endl;    return 0;}
   

代码解释

• 输入读取：读取总时间T和草药数量M，然后逐行读取每株草药的采集时间和价值。
• 动态规划数组初始化：使用一维数组dp，初始化为0，表示不选择任何草药时的价值。
• 处理每株草药：对每株草药，逆序遍历时间，更新可能的最大价值。对于每个时间j，如果草药的采集时间小于等于j，则更新dp[j]为最大价值。
• 输出结果：最终输出在总时间内的最大价值。

这种方法确保了我们在给定的时间内选择了最优的草药组合，实现了动态规划的时间和空间优化。

转载地址：http://grdgz.baihongyu.com/