[NOIP2005-普及] 采药

题目描述

山洞里有 $M$ 株草药，采第 $i$ 株需要耗时 $c_i$ 、价值为 $v_i$ 。给定总时间 $T$ ，要在总耗时不超过 $T$ 的前提下采一些草药，使采到的总价值最大。

输入格式：第一行两个整数 $T(1 \le T \le 1000)$ 和 $M(1 \le M \le 100)$ ；接下来 $M$ 行每行两个 $1 \sim 100$ 之间的整数，表示采摘一株草药的时间和它的价值。输出格式：一个整数，表示在规定时间内可以采到的草药的最大总价值。样例：输入 70 3、71 100、69 1、1 2，输出 3。

思路

这是 01 背包的定义级题目：耗时是"体积"， $T$ 是背包容量。设 $dp[t]$ 表示总耗时不超过 $t$ 时能采到的最大总价值，每株草药倒序枚举容量 $t$ 做转移 $dp[t] = \max(dp[t],\, dp[t-c_i] + v_i)$ ；倒序保证 $dp[t-c_i]$ 还是尚未考虑这株草药时的旧值，从而每株最多采一次。时间复杂度 $O(MT)$ ，空间 $O(T)$ 。

参考代码

Python 版：

python

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#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-02 06:05
# update_at: 2026-10-02 06:05

import sys


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    T = next(data)  # 总共能用来采药的时间
    M = next(data)  # 草药数目

    # dp[t]：只用已处理过的草药、耗时不超过 t 时的最大总价值
    dp = [0] * (T + 1)
    for _ in range(M):
        cost = next(data)  # 采摘这株草药需要的时间
        value = next(data)  # 这株草药的价值
        # 倒序枚举容量：保证 dp[cap - cost] 还是“没采过这株”的旧值
        for cap in range(T, cost - 1, -1):
            dp[cap] = max(dp[cap], dp[cap - cost] + value)

    print(dp[T])


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

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/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-06 13:35
 * update_at: 2026-10-06 13:35
 */
// 01 背包：dp[t] 表示总耗时不超过 t 时能采到的最大总价值
#include <iostream>
using namespace std;

typedef long long ll;

const int MAXT = 1005;

ll dp[MAXT]; // dp[t]：容量（时间）为 t 时的最大总价值
ll c[105];   // c[i]：第 i 株草药的采摘耗时
ll v[105];   // v[i]：第 i 株草药的价值

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

    ll T, M;
    cin >> T >> M;
    for (int i = 1; i <= M; i++)
        cin >> c[i] >> v[i];

    // 01 背包：每株草药只能采一次，容量必须倒序枚举，
    // 保证 dp[t - c[i]] 还是上一轮（没采过这株）的旧值
    for (int i = 1; i <= M; i++)
        for (ll t = T; t >= c[i]; t--)
            if (dp[t - c[i]] + v[i] > dp[t])
                dp[t] = dp[t - c[i]] + v[i];

    cout << dp[T] << endl;
    return 0;
}