利用0-1背包方法求解

在做这个题之前可以先看一下0-1背包的相关内容，这个题就是一个0-1背包的变形。

我也是看懂0-1背包之后才会这个题的。

主函数的开始。程序从这里执行。

    int T, M;

声明两个整数变量 T 和 M。其中：

T 表示可用的总时间。

M 表示草药的数量。

    // 将草药数组的大小调整为从0到M-1
    int herb[100][2];

定义一个二维数组 herb，大小为 100x2，用于存储最多 100 株草药的信息。每株草药有两个属性：

herb[i][0]：第 i 株草药所需的时间。

herb[i][1]：第 i 株草药的价值。

    // pack数组的第一维大小为M+1（0到M），第二维大小为T+1（0到T）
    int pack[101][1001]; // 根据实际需求调整大小

定义一个二维数组 pack，大小为 101x1001，用于存储动态规划过程中的中间结果。这里假设 M 最大为 100，T 最大为 1000。

pack[i][j] 表示前 i 株草药在不超过 j 时间内能获得的最大价值。

    scanf("%d%d", &T, &M);

从标准输入读取两个整数，分别赋值给 T 和 M。这两个值代表总时间和草药数量。

   // 读取M株草药的信息，存储在herb[0]到herb[M-1]
    for (int i = 0; i < M; i++) {
        scanf("%d%d", &herb[i][0], &herb[i][1]);
    }

通过循环读取 M 株草药的信息，每株草药需要的时间和对应的价值被存储在 herb 数组中。

   // 初始化pack数组的第一个元素为0
    pack[0][0] = 0;

初始化 pack[0][0] 为 0，表示当没有选择任何草药且时间为 0 时，最大价值为 0。

   // 初始化pack数组的第一行为0（当没有草药时，任何时间点的价值都是0）
    for (int j = 1; j <= T; j++) {
        pack[0][j] = 0;
    }

初始化 pack 数组的第一行（即不选择任何草药的情况下），对于所有时间 j，最大价值均为 0。

   // 动态规划求解最优值
    for (int i = 1; i <= M; i++) {
        for (int j = 0; j <= T; j++) {
            // 默认值为不选择当前草药的情况
            pack[i][j] = pack[i-1][j];
            if (herb[i-1][0] <= j) {
                if (pack[i][j] < herb[i-1][1] + pack[i-1][j - herb[i-1][0]]) {
                    pack[i][j] = herb[i-1][1] + pack[i-1][j - herb[i-1][0]];
                }
            }
        }
    }

这是核心的动态规划部分，分为两层循环：

对每个 pack[i][j]，首先将其初始化为不选择当前草药时的值 pack[i-1][j]。然后检查是否可以加入当前草药：

如果当前草药所需时间 herb[i-1][0] 小于等于当前时间 j，则考虑是否选择这株草药能够带来更高的价值。

如果选择该草药后的总价值更高，则更新 pack[i][j]。

外层循环遍历每一株草药（从 1 到 M）。

内层循环遍历每一个可能的时间（从 0 到 T）。

   printf("%d\n", pack[M][T]);

输出最终的结果，即在选择了 M 株草药且总时间不超过 T 的情况下，所能获得的最大价值。

整体代码如下：

#include <stdio.h>
int main() {
    int T, M;
    // 将草药数组的大小调整为从0到M-1
    int herb[100][2];
    // pack数组的第一维大小为M+1（0到M），第二维大小为T+1（0到T）
    int pack[101][1001]; // 根据实际需求调整大小
    scanf("%d%d", &T, &M);
    // 读取M株草药的信息，存储在herb[0]到herb[M-1]
    for (int i = 0; i < M; i++) {
        scanf("%d%d", &herb[i][0], &herb[i][1]);
    }
    // 初始化pack数组的第一个元素为0
    pack[0][0] = 0;
    // 初始化pack数组的第一行为0（当没有草药时，任何时间点的价值都是0）
    for (int j = 1; j <= T; j++) {
        pack[0][j] = 0;
    }
    // 动态规划求解最优值
    for (int i = 1; i <= M; i++) {
        for (int j = 0; j <= T; j++) {
            // 默认值为不选择当前草药的情况
            pack[i][j] = pack[i-1][j];
            if (herb[i-1][0] <= j) {
                if (pack[i][j] < herb[i-1][1] + pack[i-1][j - herb[i-1][0]]) {
                    pack[i][j] = herb[i-1][1] + pack[i-1][j - herb[i-1][0]];
                }
            }
        }
    }
    printf("%d\n", pack[M][T]);
    return 0;
}