g6-08125. 杂货铺清点 · 林老师的题库

题目描述

社区杂货铺要清点存货：店里有 $n$ 种货物，第 $i$ 种每件重 $w_{i}$ 、价值 $v_{i}$ 。有的货物只剩最后一件（ $k_{i} = 0$ ），有的货源充足（ $k_{i} = 1$ ），想拿几件拿几件。小杨的推车最多装 $W$ 千克，这一车货物最多能带走多少总价值？

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

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

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

2 6
0 2 3
1 3 4

第一种只剩一件，拿一件只值 3；第二种管够，拿两件重 $3 \times 2 = 6$ 、价值 $4 \times 2 = 8$ ，比混着拿更划算，所以最大总价值是 8。

$1 \leq n \leq 80$ ， $0 \leq W \leq 2000$ ， $0 \leq k_{i} \leq 1$ ， $1 \leq w_{i} \leq 200$ ， $0 \leq v_{i} \leq 5000$ 。答案在 64 位整数内。