2026模拟卷（一）T4 限时装箱

题目背景

小 Z 要搬运一批器材。他只有一个容量有限的箱子，而且必须在规定时刻前赶到下一间实验室。

题目描述

有 $n$ 件器材，编号为 $1$ 到 $n$。第 $i$ 件器材的体积为 $w_i$，放进箱子需要花费 $c_i$ 秒，价值为 $v_i$。

箱子能装下的器材体积总和不能超过 $C$，并且装箱所花费的总时间不能超过 $T$ 秒。每件器材最多只能装箱一次，不能重复装同一件器材。

请你选出一个器材子集，使它们的体积总和不超过 $C$、时间总和不超过 $T$，并且价值总和最大。输出这个最大价值总和。

输入格式

第一行三个整数 $C$、$T$、$n$，相邻两个整数之间用一个空格隔开。 接下来 $n$ 行，每行三个整数 $w_i$、$c_i$、$v_i$，相邻两个整数之间用一个空格隔开。

输出格式

共一行，一个整数，表示能获得的最大价值总和。

样例输入

6 5 4
2 1 20
5 3 30
1 2 25
3 4 30

样例输出

55

样例解释

四件器材的参数如下：

编号	体积	耗时	价值
1	2	1	20
2	5	3	30
3	1	2	25
4	3	4	30

选 1 号与 3 号：体积 $2 + 1 = 3 \le 6$，耗时 $1 + 2 = 3 \le 5$，价值 $20 + 25 = 45$。 选 1 号与 4 号：体积 $2 + 3 = 5 \le 6$，耗时 $1 + 4 = 5 \le 5$，价值 $20 + 30 = 50$。 选 2 号与 3 号：体积 $6 \le 6$，耗时 $3 + 2 = 5 \le 5$，价值 $30 + 25 = 55$。

$55$ 是最优值：若想要 $60$ 分以上的价值，唯一可能是取 $30 + 30 = 60$（2 号与 4 号），但这两件的体积是 $5 + 3 = 8 > 6$，超重；三件组合中最小体积的 1、3、4 号价值 $75$、体积 $2+1+3=6$ 恰好合法，但耗时 $1+2+4 = 7 > 5$，超时。因此答案为 55。

数据范围

子任务	分值	$n$ 的限制	$C$、$T$ 的限制
1	20	$n \le 20$	$C, T \le 20$
2		$n \le 100$	$C, T \le 100$
3	30		$C \le 500$，$T \le 500$
4			$C, T \le 500$

对于 $100\%$ 的数据，$1 \le n \le 100$，$1 \le C, T \le 500$，$1 \le w_i, c_i \le 500$，$1 \le v_i \le 10^4$。