P1048 采药

May 5, 2026 · 4 分钟阅读 · 动态规划背包问题 ·

文章目录

题目信息

字段	内容
题号	P1048
难度	橙题（普及-）
知识点	动态规划、背包问题

题目描述

辰辰是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。为此，他想拜附近最有威望的医师为师。医师为了判断他的资质，给他出了一个难题：

医师把他带到一个到处都是草药的山洞里对他说：“孩子，这个山洞里有一些不同的草药，采每一株药需要一些时间，每一株药也有它自身的价值。我会给你一段时间，在这段时间里，你可以采到一些草药。如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大。”

现在已知山洞里各株草药采药需要花费的时间、该株草药的价值，以及你总共可以用于采药的时间。求在规定时间内可以采到的草药的最大总价值。

输入格式：第一行两个整数 T（总时间）和 M（草药数量），接下来 M 行每行两个整数，分别表示采该株药需要花费的时间和该株药的价值。

输出格式：一个整数，表示在规定时间内可以采到的草药的最大总价值。

解题思路

核心思想

这是0-1 背包问题的经典模板：

每种草药要么采（选），要么不采（不选），不能重复采
目标：在总时间 T 内，使总价值最大

DP 状态定义

dp[j]：用恰好 j 分钟采药，能获得的最大价值。

状态转移方程

对于第 i 株药（耗时 w[i]，价值 v[i]）：

dp[j] = max(dp[j], dp[j - w[i]] + v[i])

含义：不采第 i 株药，价值是 dp[j]；采第 i 株药，价值是 dp[j - w[i]] + v[i]，取较大者。

为什么内层循环要倒序？

for (int j = T; j >= w[i]; j--)

倒序遍历是为了保证每个物品只能被选一次：

如果正序遍历，在更新 dp[j] 时，dp[j - w[i]] 可能已经被本轮更新过了（即第 i 个物品被选了两次），变成了完全背包
倒序遍历时，dp[j - w[i]] 一定还是上一轮（i-1）的值，保证了每个物品最多选一次

完整代码

C++

#include <iostream>
#include <algorithm>

using namespace std;

const int kMaxT = 10001;
const int kMaxM = 101;

int w[kMaxM];   // 每株药需要的时间
int v[kMaxM];   // 每株药的价值
int dp[kMaxT];  // dp[j]：用 j 分钟的最大价值

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

    int t, m;
    cin >> t >> m;

    for (int i = 1; i <= m; i++) {
        cin >> w[i] >> v[i];
    }

    // 0-1 背包：外层遍历物品，内层倒序遍历容量
    for (int i = 1; i <= m; i++) {
        for (int j = t; j >= w[i]; j--) {
            dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
        }
    }

    cout << dp[t] << "\n";
    return 0;
}

关键代码讲解

1. 数组大小设定

const int kMaxT = 10001;  // T ≤ 1000，保守取 10001
const int kMaxM = 101;    // M ≤ 100，保守取 101

洛谷 P1048 的数据范围是 T ≤ 1000，M ≤ 100，数组开大一点防止边界溢出。

2. 倒序遍历的核心

for (int j = t; j >= w[i]; j--)
    dp[j] = max(dp[j], dp[j - w[i]] + v[i]);

j >= w[i]：剩余时间不够采这株药，直接跳过
倒序保证了 dp[j - w[i]] 是上一轮的状态（未选第 i 株药时的最优解）

3. 初始化

dp 数组全局定义，默认全为 0，表示一开始任何时间都不采药，价值为 0。这是 0-1 背包的标准初始化方式。

复杂度分析

方法	时间复杂度	空间复杂度
一维 DP（空间优化）	O(T × M)	O(T)

T ≤ 1000，M ≤ 100，最大 10^5 次运算，洛谷限时完全够用
空间从 O(T × M) 优化到了 O(T)，节省了大量内存

易错点

内层循环必须倒序：正序会变成完全背包（物品可重复选），这是最容易错的地方
j 的下界是 w[i] 不是 0：剩余时间比采这株药的时间还少时，这株药根本采不了
数组大小：dp 的大小要至少 T + 1，用 10001 比较安全
ios::sync_with_stdio(false)：洛谷输入量较大，必须关闭同步加速

其他语言解法

Python

"""P1048 采药 - Python 实现（0-1 背包）"""
from typing import List


def solve() -> None:
    """读取输入，计算在 T 时间内可采药的最大总价值"""
    t, m = map(int, input().split())
    w: List[int] = [0] * (m + 1)
    v: List[int] = [0] * (m + 1)

    for i in range(1, m + 1):
        w[i], v[i] = map(int, input().split())

    # dp[j]：用 j 分钟的最大价值
    dp: List[int] = [0] * (t + 1)

    for i in range(1, m + 1):
        # 倒序遍历，保证每个物品只选一次
        for j in range(t, w[i] - 1, -1):
            dp[j] = max(dp[j], dp[j - w[i]] + v[i])

    print(dp[t])


if __name__ == "__main__":
    solve()

Java

import java.io.IOException;

public class Main {
    // 洛谷强制要求类名为 Main，禁止使用 Scanner，用 BufferedInputStream
    private static final byte[] BUFFER = new byte[1 << 16];
    private static int ptr = 0;
    private static int len = 0;

    private static int read() throws IOException {
        if (ptr >= len) {
            len = System.in.read(BUFFER);
            ptr = 0;
            if (len <= 0) return -1;
        }
        return BUFFER[ptr++];
    }

    private static int readInt() throws IOException {
        int c, val = 0;
        do {
            c = read();
        } while (c <= ' ' && c != -1);
        boolean neg = (c == '-');
        if (neg) c = read();
        while (c > ' ') {
            val = val * 10 + (c - '0');
            c = read();
        }
        return neg ? -val : val;
    }

    public static void main(String[] args) throws IOException {
        int t = readInt();
        int m = readInt();

        int[] w = new int[m + 1];
        int[] v = new int[m + 1];
        for (int i = 1; i <= m; i++) {
            w[i] = readInt();
            v[i] = readInt();
        }

        int[] dp = new int[t + 1];
        for (int i = 1; i <= m; i++) {
            for (int j = t; j >= w[i]; j--) {
                dp[j] = Math.max(dp[j], dp[j - w[i]] + v[i]);
            }
        }

        System.out.println(dp[t]);
    }
}

Go

package main

import (
    "bufio"
    "fmt"
    "os"
)

func main() {
    in := bufio.NewReader(os.Stdin)

    var t, m int
    fmt.Fscan(in, &t, &m)

    w := make([]int, m+1)
    v := make([]int, m+1)
    for i := 1; i <= m; i++ {
        fmt.Fscan(in, &w[i], &v[i])
    }

    dp := make([]int, t+1)
    for i := 1; i <= m; i++ {
        for j := t; j >= w[i]; j-- {
            if dp[j] < dp[j-w[i]]+v[i] {
                dp[j] = dp[j-w[i]] + v[i]
            }
        }
    }

    fmt.Println(dp[t])
}

JavaScript

'use strict';

/**
 * 0-1 背包：在 T 时间内采药，求最大总价值
 */
function main() {
    const input = require('fs').readFileSync(0, 'utf8').trim().split(/\s+/).map(Number);
    let idx = 0;
    const t = input[idx++];
    const m = input[idx++];

    const w = [0];
    const v = [0];
    for (let i = 0; i < m; i++) {
        w.push(input[idx++]);
        v.push(input[idx++]);
    }

    /** @type {number[]} */
    const dp = new Array(t + 1).fill(0);

    for (let i = 1; i <= m; i++) {
        for (let j = t; j >= w[i]; j--) {
            dp[j] = Math.max(dp[j], dp[j - w[i]] + v[i]);
        }
    }

    console.log(dp[t]);
}

main();