[NOIP 2005 普及组] 采药

题意

给出总时间 T 和 M 株草药。

第 i 株草药有：

采它需要的时间
它本身的价值

要求在总采药时间不超过 T 的前提下，让采到的草药总价值最大。每株草药最多采一次。

思路

先看最直接的暴力：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60// brute.cpp：小数据暴力解，使用 01 序列枚举每株草药选或不选。
#include <bits/stdc++.h>
using namespace std;

const int MAXM = 1005;

int total_time;         // 总可用时间
int herb_count;         // 草药数量
int need_time[MAXM];    // 每株草药需要的时间
int herb_value[MAXM];   // 每株草药的价值
int choose_herb[MAXM];  // choose_herb[i] = 0/1，表示第 i 株草药不采/采
int best_answer;        // 当前找到的最大总价值

bool check() {
    int used_time = 0;
    for (int i = 1; i <= herb_count; i++) {
        if (choose_herb[i] == 1) used_time += need_time[i];
    }
    return used_time <= total_time;
}

int calc_answer() {
    int total_value = 0;
    for (int i = 1; i <= herb_count; i++) {
        if (choose_herb[i] == 1) total_value += herb_value[i];
    }
    return total_value;
}

void dfs_choose(int dep) {
    if (dep == herb_count + 1) {
        if (check()) {
            int value = calc_answer();
            if (best_answer < value) best_answer = value;
        }
        return;
    }

    // 第 dep 株草药的 01 选择：0 不采，1 采。
    for (int i = 0; i <= 1; i++) {
        choose_herb[dep] = i;
        dfs_choose(dep + 1);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> total_time >> herb_count;
    for (int i = 1; i <= herb_count; i++) {
        cin >> need_time[i] >> herb_value[i];
    }

    best_answer = 0;
    dfs_choose(1);

    cout << best_answer << '\n';
    return 0;
}

brute.cpp 把每株草药看成一个 01 选择：choose_herb[i] = 0/1 表示不采或采。递归先生成完整选择，叶子节点再检查总时间是否超限，并统计总价值。

这个做法显然正确，但复杂度是 $O(2^M)$ ，只能做小数据验证。

这题本质上就是最基础的 0/1 背包：

每株草药是一个物品
采药时间是“重量”
草药价值是“价值”

设：

dp[t] 表示总时间不超过 t 时，能取得的最大总价值

加入一株草药 (time_i, value_i) 时：

不采它：状态不变
采它：从 dp[t - time_i] 转移过来，再加上 value_i

所以转移是：

dp[t] = max(dp[t], dp[t - time_i] + value_i)

由于每株草药只能采一次，时间维必须倒序枚举。

状态表

这张表说明状态的含义：

状态	含义
`dp[t]`	总时间不超过 `t` 时的最大总价值

从这个定义可以看出，DP 只关心“用了多少时间”以及“能取得多少价值”，不需要记录具体选了哪些草药。因此一维状态就足够。

最后输出 dp[T] 即可。

DP 公式

设 $dp_t$ 表示总时间不超过 $t$ 时能取得的最大总价值。处理第 $i$ 株草药时：

dp_t=\max(dp_t,\ dp_{t-time_i}+value_i)

其中 $t\geqslant time_i$ 。因为每株草药最多采一次， $t$ 必须倒序枚举。最终答案为：

dp_T

公式解释：dp_t 保存时间上限为 t 时的最大价值。选择当前草药会占用 time_i 时间，所以只能从剩余时间 t-time_i 的最优值转移过来。

样例 DP 表格

以样例为例： $T = 70, M = 3$ ，三株草药为 $(71, 100), (69, 1), (1, 2)$ 。

处理草药	$time_i$	$value_i$	$dp$ 变化（关键容量）
初始	—	—	$dp_{0 \sim 70} = 0$
草药 1	71	100	71 > 70，无法放入， $dp$ 不变
草药 2	69	1	$dp_{69} = 1, dp_{70} = 1$
草药 3	1	2	$dp_1 = 2, dp_{69} = 2, dp_{70} = \max(1, dp_{69}+2) = 3$

答案 $dp_{70} = 3$ ，对应采草药 2 和草药 3（耗时 $69+1=70$ ，价值 $1+2=3$ ）。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41#include <bits/stdc++.h>
using namespace std;

const int MAXM = 1005;
const int MAXT = 10005;

int total_time;         // 总可用时间
int herb_count;         // 草药数量
int need_time[MAXM];    // 每株草药需要的时间
int herb_value[MAXM];   // 每株草药的价值
int dp[MAXT];           // dp[t] = 总时间不超过 t 时的最大总价值

void read_input() {
    cin >> total_time >> herb_count;
    for (int i = 1; i <= herb_count; i++) {
        cin >> need_time[i] >> herb_value[i];
    }
}

void solve() {
    memset(dp, 0, sizeof(dp));

    for (int i = 1; i <= herb_count; i++) {
        // 倒序枚举时间，保证每株草药最多只采一次。
        for (int t = total_time; t >= need_time[i]; t--) {
            dp[t] = max(dp[t], dp[t - need_time[i]] + herb_value[i]);
        }
    }

    cout << dp[total_time] << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    read_input();
    solve();

    return 0;
}

复杂度

时间复杂度： $O(MT)$
空间复杂度： $O(T)$

总结

这题是 0/1 背包最标准的入门模型：

物品只能选一次
容量受一个维度限制
目标是最大化总价值

以后看到“时间不超过多少、收益尽量大、每个对象最多用一次”这类条件，就可以优先往一维 0/1 背包上想。

一图流解析

这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。