疯狂的采药

题意

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

第 i 种草药需要时间 cost[i]
第 i 种草药带来价值 value[i]
每种草药可以无限次采摘

要求在总时间不超过 T 的前提下，让总价值最大。

这张表把题目翻译成背包模型：

原题对象	背包含义
一种草药	一个可以重复使用的物品
采摘时间	物品重量
草药价值	物品价值
总时间 `T`	背包容量

从表里可以看出，本题是完全背包，而不是 0/1 背包。

思路

先看最直接的暴力：

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
61
62
63#include <bits/stdc++.h>
using namespace std;

// brute.cpp：小数据暴力解，用来帮助理解题意并辅助对拍。

const int MAXN = 10005;

int t, m;
int cost[MAXN];
int value[MAXN];
int choose_count[MAXN]; // choose_count[i] 表示第 i 种草药取多少次
long long answer;

bool check() {
    int used_time = 0;
    for (int i = 1; i <= m; i++) {
        used_time += choose_count[i] * cost[i];
    }
    return used_time <= t;
}

long long calc_answer() {
    long long total_value = 0;
    for (int i = 1; i <= m; i++) {
        total_value += 1LL * choose_count[i] * value[i];
    }
    return total_value;
}

// 依次枚举每种草药可以取多少次，叶子节点统一检查总时间。
void dfs_choose(int dep) {
    if (dep == m + 1) {
        if (check()) {
            long long current_value = calc_answer();
            if (answer < current_value) answer = current_value;
        }
        return;
    }

    int limit = t / cost[dep];
    for (int cnt = 0; cnt <= limit; cnt++) {
        choose_count[dep] = cnt;
        dfs_choose(dep + 1);
    }
}

void read_input() {
    cin >> t >> m;
    for (int i = 1; i <= m; i++) {
        cin >> cost[i] >> value[i];
    }
}

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

    read_input();
    dfs_choose(1);
    cout << answer << '\n';

    return 0;
}

brute.cpp 把每种草药取多少次看成一层选择：choose_count[i] 表示第 i 种草药采摘次数。递归先生成完整计数序列，叶子节点再检查总时间是否超限，并统计总价值。

这个做法显然正确，但复杂度很高，只适合小数据验证。

关键观察是：同一种草药可以无限次采摘，所以和 0/1 背包相比，转移时不能只看上一轮物品状态。

于是设：

dp[j] 表示时间不超过 j 时的最大奖励

这张表说明状态定义：

状态	含义
`dp[j]`	时间不超过 `j` 时的最大奖励

处理第 i 种草药 (cost[i], value[i]) 时：

不选它：dp[j] 保持原值
选它：从 dp[j - cost[i]] 转移过来，再加上 value[i]

因为同一种草药可以继续被重复使用，所以这里必须按时间正序枚举：

dp[j] = max(dp[j], dp[j - cost[i]] + value[i])

正序枚举时，dp[j - cost[i]] 可能已经在本轮被更新过，这正好允许当前草药再次被选。

最后输出 dp[T] 即可。

DP 公式

设 $dp_j$ 表示时间不超过 $j$ 时能获得的最大价值。处理耗时 $cost_i$ 、价值 $value_i$ 的草药时：

dp_j=\max(dp_j,\ dp_{j-cost_i}+value_i)

同一种草药可以无限采，所以 $j$ 正序枚举，让本轮更新后的状态继续参与转移。最终答案为：

dp_T

公式解释：同一种草药可以无限采，所以当前轮更新出的 dp_{j-cost_i} 还能继续用于同一种草药。正序枚举容量正是为了允许这种重复选择。

样例 DP 表格

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

处理草药	$cost_i$	$value_i$	$dp$ 变化（关键容量）
初始	—	—	$dp_{0 \sim 70} = 0$
草药 1	71	100	71 > 70，无法放入， $dp$ 不变
草药 2	69	1	$dp_{69} = 1, dp_{70} = 1$ （只能采 1 次）
草药 3	1	2	正序扫描，可采 70 次： $dp_1=2, dp_2=4, \dots, dp_{70}=140$

答案 $dp_{70} = 140$ ，对应全部采草药 3 共 70 次（耗时 $70 \times 1 = 70$ ，价值 $70 \times 2 = 140$ ）。

代码

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#include <bits/stdc++.h>
using namespace std;

const int MAXN = 10005;

int t, m;
int cost[MAXN];
int value[MAXN];
vector<long long> dp; // dp[j] 表示时间不超过 j 时的最大奖励

void read_input() {
    cin >> t >> m;
    for (int i = 1; i <= m; i++) {
        cin >> cost[i] >> value[i];
    }
}

void solve() {
    dp.assign(t + 1, 0);

    for (int i = 1; i <= m; i++) {
        // 完全背包可以重复选同一种草药，所以容量必须正序枚举。
        for (int j = cost[i]; j <= t; j++) {
            dp[j] = max(dp[j], dp[j - cost[i]] + value[i]);
        }
    }

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

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

    read_input();
    solve();

    return 0;
}

复杂度

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

总结

这题是完全背包的标准模板：

每种物品可以选无限次
容量正序枚举
目标是最大化总价值

以后看到“同一种对象可以重复使用”这类条件时，就要先想到完全背包。

一图流解析

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

目录

题意

思路

DP 公式

样例 DP 表格

代码

复杂度

总结

一图流解析