g6-08079. 露营装备 · 林老师的题库

题目描述

小杨要去山上住两天，正往行囊里装东西：家里有 $n$ 种装备，第 $i$ 种装备每件重 $w_{i}$ 、价值 $v_{i}$ ，家里只有 $c_{i}$ 件可用——可能一件都没有，也可能多到根本带不完，总之每种最多带 $c_{i}$ 件。他的行囊最多承重 $W$ 。求能带走的最大总价值。

第一行两个整数 $n$ 、 $W$ 。

接下来 $n$ 行，每行三个整数 $w_{i}$ 、 $v_{i}$ 、 $c_{i}$ 。

输出一个整数，表示最大总价值。

3 10
2 3 2
3 4 1000000000
4 5 1

重量 $2$ 的取 $2$ 件、重量 $3$ 的取 $2$ 件：总重量 $2 + 2 + 3 + 3 = 10$ ，总价值 $3 + 3 + 4 + 4 = 14$ ；第二种装备虽然标着很多件，但行囊只装得下 $3$ 件，取 $2$ 件更划算。

$1 \leq n \leq 30$ ， $0 \leq W \leq 500$ ， $1 \leq w_{i} \leq 1000$ ， $0 \leq v_{i} \leq 1 0^{9}$ ， $0 \leq c_{i} \leq 1 0^{9}$ 。保证答案不超过 $1 0^{18}$ 。