引言

题目要求

• 输入格式
  • 第一行：两个整数 T（总时间）和 M（草药数量），如 70 3（表示有70分钟，3株草药）。
  • 后续 M 行：每行两个整数，时间 和 价值，如 50 60（表示这株药需要50分钟采摘，价值60）。
• 限制条件
  • 你只有 T 分钟的时间，不能超时。
  • 每种草药 只能采一次（要么采，要么不采，不能拆分）。
• 目标
  • 合理选择采哪些草药，使得 总时间不超过T，同时让 总价值最大化。

输入

70 3

50 60

30 40

20 30

输出

3

思路

定义变量，创建数组存储草药价值及对应的时间

int T;//总时间

int M；//草药数量

int time[1000];//根据题目要求限制长度

int value[1000];

输入

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

for(int i=0;i<M;i++){

    scanf("%d %d",&time[i],&value[i];

};

再创建一个数组长度为总的时间 T，该数组用来表示 T 内的某一时间 t 下的最大价值，例如 dp[7]=100，表示时间为 7 时总价值为 100。并且利用 memset 函数对 dp 数组进行初始化，即把里面每一个数都填充为 0。

int dp[T]

memset(dp, 0, sizeof(dp));

遍历每一种草药

for(int i=0;i<M;i++){};

从最大的时间开始遍历，直到剩余时间已经不足当前药草的时间。

for(int i=0;i<M;i++){
    for(int j=T;j>=time[i];T--){
    };
};

如果当前药草再采集后为最大值就更新 dp 数组的值

dp[j-time[i]] 是当总时间为 j 时，采集了第 i 颗药草后，剩下时间可以得到的价值

然后在加上这第 i 颗药草的价值，如果大于原来 j 时间的值就更新一下。

for(int i=0;i<M;i++){//遍历每一种草药

    for(int j=T;j>=time[i];T--){//确保能够采集当前的药草

        if(dp[j-time[i]]+value[i]>dp[j]){//如果采集后更大就更新一下

            dp[j]=dp[j-time[i]]+value[i];

        };

    };

};

核心就是 dp[t]表示时间t能获得的最大价值

分布模拟

T=7 (总时间)

M=4 (草药数量)

草药数据：

1. time=2, value=3
2. time=3, value=4
3. time=4, value=5
4. time=1, value=2

dp 数组初始化为 [0, 0, 0, 0, 0, 0, 0, 0]（容量 0~7，共8个位置）

第1株草药（time=2, value=3）

1. t=7

剩余时间 j - time[1] = 7 - 2 = 5

当前选择的价值 = dp[5] + value[1] = 0 + 3 = 3

原 dp[7] = 0，3 > 0 → 更新 dp[7]=3

2. t=6

j- time[1] = 6 - 2 = 4

dp[4] + value[1] = 0 + 3 = 3 > dp[6]=0 → dp[6]=3