j01727. 二维费用背包 · 林老师的题库

题目描述

小 P 的背包有两个限制：总重量不能超过 $V$ ，总体积不能超过 $M$ 。

现在有 $n$ 件物品，第 $i$ 件的重量是 $a_{i}$ 、体积是 $b_{i}$ 、价值是 $c_{i}$ ，每件至多选一次。

在重量不超过 $V$ 、体积不超过 $M$ 的双重限制下，请计算能获得的最大价值总和。

第一行三个整数 $V$ 、 $M$ 和 $n$ ：重量上限、体积上限、物品件数。

接下来 $n$ 行，每行三个整数 $a_{i}$ 、 $b_{i}$ 和 $c_{i}$ ，依次表示第 $i$ 件物品的重量、体积与价值。

一行一个整数，表示两种限制下能获得的最大价值总和。

输入

5 6 2
3 2 10
2 3 12

输出

两件都拿：总重量 $3 + 2 = 5 \leq 5$ 、总体积 $2 + 3 = 5 \leq 6$ ，价值 $10 + 12 = 22$ ，两种限制都满足。

如果只拿一件（价值 $10$ 或 $12$ ），价值更低。