P1616 疯狂的采药

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

文章目录

题目信息

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

题目描述

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

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

此题与 P1048 采药的不同之处在于：每种草药可以无限制地疯狂采摘。

输入格式

第一行有两个整数 T（总时间）和 M（草药种类数）
接下来 M 行，每行两个整数 a_i, b_i，分别表示采摘第 i 种草药所需的时间 a_i 和它价值 b_i

输出格式

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

数据范围

变量	范围
`T`	`0 ≤ T ≤ 10^7`
`M`	`0 ≤ M ≤ 10^4`
`a_i`	`0 < a_i ≤ 10^7`
`b_i`	`0 < b_i ≤ 10^7`

样例

输入

输出

解释：时间 T=70，有 3 种草药。第一种需要 71 时间（采不了），第二种价值 1 但耗时 69，第三种耗时 1 价值 2，可以采 70 次，总价值 140。

解题思路

核心思想

本题与 P1048「采药」的唯一区别在于：每种草药可以采摘无限次。这使得它从一个 0-1 背包问题变成了一个完全背包（Complete Knapsack）问题。

完全背包与 0-1 背包的关键区别

问题类型	每种物品	内层循环方向	状态转移
0-1 背包	只能选一次	逆序 `j` 从 `T → a_i`	防止重复选取
完全背包	可选无限次	正序 `j` 从 `a_i → T`	允许重复选取

为什么正序遍历就能实现「无限次选取」？

以 dp[j] = max(dp[j], dp[j-a_i] + b_i) 为例：

当 j 正序递增时，dp[j-a_i] 在此轮中已经计算过（因为 j-a_i < j，且正序下 j-a_i 比 j 先被更新）
这意味着 dp[j-a_i] 可能已经包含了一份 a_i，再用它更新 dp[j]，就相当于「再选一次 a_i」
以此类推，同一轮中可以多次选 a_i → 实现无限次选取 ✅

状态定义

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

状态转移方程

dp[j] = max(dp[j], dp[j - a_i] + b_i), j ≥ a_i

完整代码

C++

#include <cstdio>
#include <algorithm>

typedef long long ll;

const int kMaxT = 10000005;
ll dp[kMaxT];

int main() {
    int t = 0, m = 0;
    scanf("%d%d", &t, &m);

    for (int i = 1; i <= m; ++i) {
        int a = 0, b = 0;
        scanf("%d%d", &a, &b);
        // 完全背包：正序遍历，允许重复选取
        for (int j = a; j <= t; ++j) {
            dp[j] = std::max(dp[j], dp[j - a] + b);
        }
    }

    printf("%lld\n", dp[t]);
    return 0;
}

原提交代码说明：你提供的代码中 dp[j] = dp[j]; 是一句无效语句（将自身赋值给自身），实际上 j < a[i] 时什么也不做，可以直接从 j = a[i] 开始循环，简化代码。

关键代码讲解

为什么内层循环从 `j = a[i]` 开始？

当 j < a_i 时，当前草药 i 连一次都采不了，无需更新 dp[j]，初始值（即上一轮的结果）已经是最优的。直接从 j = a_i 开始既正确又高效。

原代码的问题分析

你提交的代码：

for (int j = 0; j <= T; j++) {
    if (j < a[t]) {
        dp[j] = dp[j];  // ❌ 无效语句，等于什么都不做
    } else {
        dp[j] = max(dp[j], dp[j - a[t]] + b[t]);
    }
}

问题：

dp[j] = dp[j]; 是无效操作，编译器可能会优化掉，应直接删除（或让循环从 j = a[t] 开始）
多余的头文件：#include <queue/stack/set/map/vector/cmath> 均未使用
const int maxn = 1e7 + 5 定义过大，int a[maxn] 占用约 40MB，在栈上分配可能导致段错误，应改为局部变量或用 vector

修正后的写法（更简洁）：

for (int j = a[i]; j <= t; ++j) {
    dp[j] = std::max(dp[j], dp[j - a[i]] + b[i]);
}

复杂度分析

方法	时间复杂度	空间复杂度
一维完全背包	`O(M * T)`	`O(T)`

M ≤ 10^4，T ≤ 10^7，最坏情况下 O(M * T) 约 10^11 会超时
但实际上洛谷数据梯度设计合理，且 C++ 优化后可以通过
如仍超时，可进一步用「单调队列优化完全背包」，将复杂度降为 O(M * T) 的常数级优化

易错点

内层循环方向搞反：写成逆序 for (j = T; j >= a[i]; j--) 就变成 0-1 背包，只能通过每种草药一次，与题意不符！
dp 数组类型要用 long long：M=10^4，b_i=10^4 时，最大价值可达 10^4 × 10^7 = 10^11，超出 int 范围。
数组大小要开够：T 最大 10^7，dp 数组需要 10^7+5 大小的 long long，约 80MB，注意内存限制（洛谷此题为 256MB，刚好够用）。
不要用 cin/cout 读入大量数据：(M ≤ 10^4 不算大，但配合 T 较大时 cin 较慢，建议用 scanf。

其他语言解法

Python

import sys

def main() -> None:
    data = sys.stdin.buffer.read().split()
    t = int(data[0])
    m = int(data[1])

    dp = [0] * (t + 1)
    idx = 2

    for _ in range(m):
        a = int(data[idx]); b = int(data[idx + 1]); idx += 2
        # 完全背包：正序遍历
        for j in range(a, t + 1):
            if dp[j - a] + b > dp[j]:
                dp[j] = dp[j - a] + b

    print(dp[t])

if __name__ == "__main__":
    main()

⚠️ Python 情况下 T 最大 10^7 会导致内存和时间超时，建议仅用于小数据理解算法。

Java

import java.io.BufferedInputStream;
import java.io.InputStream;
import java.io.DataInputStream;

public class Main {
    private static int nextInt(InputStream in) throws Exception {
        int c, val = 0;
        while ((c = in.read()) <= 32) {}
        do { val = val * 10 + (c - '0'); } while ((c = in.read()) > 32);
        return val;
    }

    public static void main(String[] args) throws Exception {
        InputStream in = new BufferedInputStream(System.in);
        int t = nextInt(in);
        int m = nextInt(in);

        long[] dp = new long[t + 1];
        for (int i = 0; i < m; i++) {
            int a = nextInt(in);
            int b = nextInt(in);
            for (int j = a; j <= t; j++) {
                if (dp[j - a] + b > dp[j]) {
                    dp[j] = dp[j - a] + b;
                }
            }
        }
        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)

	dp := make([]int64, t+1)
	for i := 0; i < m; i++ {
		var a, b int
		fmt.Fscan(in, &a, &b)
		for j := a; j <= t; j++ {
			v := dp[j-a] + int64(b)
			if v > dp[j] {
				dp[j] = v
			}
		}
	}
	fmt.Println(dp[t])
}

注：Go 语言的 int 在 64 位系统上是 64 位，但显式使用 int64 更安全。

JavaScript (Node.js)

'use strict';

const fs = require('fs');
const data = fs.readFileSync(0, 'utf-8').trim().split(/\s+/).map(Number);

const t = data[0];
const m = data[1];
const dp = new Array(t + 1).fill(0);

let idx = 2;
for (let i = 0; i < m; i++) {
    const a = data[idx++];
    const b = data[idx++];
    for (let j = a; j <= t; j++) {
        const v = dp[j - a] + b;
        if (v > dp[j]) dp[j] = v;
    }
}

console.log(dp[t]);

⚠️ Node.js 在 T=10^7 时同样会超时/超内存，仅用于小数据验证算法正确性。