采药 - 题目列表

题目描述

辰辰进山洞采药，总时间上限 $T$ （ $1\le T\le 1000$ ），面前有 $M$ 株（ $1\le M\le 100$ ），每株耗时 $\text{cost}_i$ 、价值 $\text{value}_i$ （均在 $[1,100]$ ），每株至多采一次。输入第一行是 $T$ 、 $M$ ，接下来 $M$ 行各给一株的 $(\text{cost}, \text{value})$ ，输出总时间不超过 $T$ 时能采到的最大总价值。样例： $T=70$ 、草药 $(71,100),(69,1),(1,2)$ → 输出 $3$ 。

思路

一维 0/1 背包：dp[j] 表示时间上限 $j$ 下的最大价值，初始化为 $0$ ；按草药顺序遍历，容量从 $T$ 倒序扫到 $\text{cost}$ ，令 dp[j] = max(dp[j], dp[j - cost] + value)，倒序保证每株只入一次；答案为 dp[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#!/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-09-30 03:38
# update_at: 2026-09-30 03:38

import sys


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    limit = next(data)  # 题面的 T：可用于采药的总时间
    count = next(data)  # 题面的 M：草药株数

    # dp[j] = 限定时间 j 内能采到的最大总价值；容量维度倒序保证每株草药只用一次
    dp = [0] * (limit + 1)
    for _ in range(count):
        cost = next(data)   # 采摘这株草药需要的时间
        value = next(data)  # 这株草药的价值
        for j in range(limit, cost - 1, -1):
            dp[j] = max(dp[j], dp[j - cost] + value)

    print(dp[limit])


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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54/**
 * 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-04 22:12
 * update_at: 2026-10-04 22:12
 */

// main.cpp：采药（roj 1290）的 0/1 背包一维滚动解。
// 容量上限 T <= 1000，物品数 M <= 100，单件花费与价值均在 [1,100]，结果用 long long 兜住。

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXT = 1005; // 容量上限 + 1，足够放下题目给的最大 T

ll T;          // 总可用时间（背包容量）
ll M;          // 草药总数
ll dp[MAXT];   // dp[j] = 限定时间 j 内能采到的最大价值；只用一维滚动数组

void read_input() {
    cin >> T >> M;
}

void solve() {
    // 初始化：所有容量下的最优价值都为 0。
    for (ll j = 0; j <= T; j++) dp[j] = 0;

    for (ll i = 0; i < M; i++) {
        ll cost;   // 这株草药的采摘时间
        ll value;  // 这株草药的价值
        cin >> cost >> value;

        // 容量倒序扫描，保证 dp[j - cost] 还是上一轮（第 i-1 株）的结果，
        // 从而实现"每株草药至多取一次"的 0/1 语义。
        for (ll j = T; j >= cost; j--) {
            dp[j] = max(dp[j], dp[j - cost] + value);
        }
    }

    cout << dp[T] << "\n";
}

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

    read_input();
    solve();

    return 0;
}

采药

目录

题目描述

思路

参考代码