g6-08082. 校运会奖品 · 林老师的题库

题目描述

学校要开运动会，小杨负责采购奖品。一共有 $n$ 种奖品，第 $i$ 种奖品单价 $w_{i}$ 元、每件能带来 $v_{i}$ 点吸引力，仓库里这种奖品只有 $c_{i}$ 件，最多买这么多件，也可以一件都不买。采购预算为 $W$ 元。求能获得的最大总吸引力。

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

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

输出一个整数，表示最大总吸引力。

买 $2$ 件单价 $2$ 的、 $1$ 件单价 $3$ 的、 $1$ 件单价 $5$ 的奖品：花 $2 \times 2 + 3 + 5 = 12$ 元，吸引力 $3 \times 2 + 4 + 6 = 16$ ，是所有买法里最高的。

$1 \leq n \leq 100$ ， $0 \leq W \leq 1000$ ， $1 \leq w_{i} \leq 1000$ ， $0 \leq v_{i} \leq 1000$ ， $0 \leq c_{i} \leq 20$ 。