飞船载荷

题目描述

星际运输舰“远航号”正准备起航前往遥远的半人马座。飞船的储物舱面临着两个严格的物理限制：

1. 最大承重上限 $W$ 单位重量。
2. 最大容积上限 $V$ 单位容积。

港口共有 $N$ 种补给箱，每种补给箱的数量都是无限的。第 $a$ 种补给箱的属性如下：

• 单个补给箱重量为 $w_i$。
• 单个补给箱容积为 $c_i$（注意：这里使用 $c_i$ 代表容积）。
• 单个补给箱能提供的生存点数为 $p_i$。

作为货物调度员，你的任务是在不超过飞船承重和容积上限的前提下，决定每种补给箱的装载数量，使得飞船能携带的总生存点数最大。

输入格式

第一行包含三个整数 $N, W, V$，分别表示素材种类数、最大重量和最大容积。

接下来的 $N$ 行，每行包含三个整数 $w_i, c_i, p_i$，分别表示第 $i$ 种素材的重量、容积和生存点。

输出格式

输出一个整数，表示在限制范围内能获得的最大生存点数。

输入输出样例 #1

输入 #1

2 10 10
3 4 10
4 3 12

输出 #1

34

样例 1 说明

选择两份第 2 种补给箱（重 8，容 6，生存点 24）和一份第 1 种（重 3，容 4，生存点 10）？不，这样重量 11 超过了。 最优方案：选择两份第 2 种（重 8，容 6，生存点 24）？还是更多？ 如果选两份第 2 种，还余重 2 容 4，无法装别的。总分 24。 如果选一份第 1 种和两份第 2 种？11 > 10。 如果选两份第 1 种，重 6 容 8，分 20。还余重 4 容 2，装不下别的。 如果选一份第 1 种和一份第 2 种，重 7 容 7，分 22。余重 3 容 3，刚好可以再装一份第 1 种（重 3 容 4 -> 容积超）。 最优应该是：两份第 2 种（重 8 容 6）+ 一份重 2 容 1 的物件（本题没有）。 手动模拟：(w=4, c=3, p=12) $\times$ 2 + (w=3, c=4, p=10) $\times$ 0 = 24. Wait, let's re-check 01 样例. If M=10, w1=3, w2=4, v1=5, v2=7. 3x2+4x1=10, 5x2+7=17. 这里 W=10, V=10. (4,3,12) $\times$ 2 = (8,6,24) -> OK (4,3,12) $\times$ 3 = (12,9,36) -> 重超 (3,4,10) $\times$ 2 = (6,8,20) -> OK (3,4,10) $\times$ 1 + (4,3,12) $\times$ 1 = (7,7,22) -> OK (4,3,12) $\times$ 2 + nothing = 24. (3,4,10) $\times$ 1 + (4,3,12) $\times$ 2 = (11,10,34) -> 重超. 最优为 24。（样例数值需严谨，我重新设计样例数据）。

修正样例数据：

输入：

2 8 8
2 3 10
3 2 12

方案：

• 2 个第 1 种：(4, 6, 20)
• 2 个第 2 种：(6, 4, 24)
• 1 个第 1 种 + 2 个第 2 种：(2+6, 3+4, 10+24) = (8, 7, 34) -> 合法且最大。 输出：

34

数据范围

对于 $60\%$ 的数据，$1 \le N, W, V \le 50$。

对于 $100\%$ 的数据，$1 \le N \le 200$，$1 \le W, V \le 200$，$1 \le w_i, c_i \le 200$，$1 \le p_i \le 10^5$。

建议

三刷