g6-08096. 多装几件 · 林老师的题库

题目描述

搬家前小杨要装箱：有 $n$ 种物品，第 $i$ 种每件重 $w_{i}$ 、价值 $v_{i}$ ，每种物品都很多件，想装几件装几件；箱子最多承重 $V$ 。他想让箱子里物品的总价值最大；如果有好几种装法都能达到最大价值，他希望箱子里的件数尽量多。请输出最大总价值，以及达到它时最多的件数。

第一行两个整数 $n, V$ 。接下来 $n$ 行，每行两个整数 $w_{i}, v_{i}$ 。

一行两个整数，用空格分隔：最大总价值、达到该价值的最多件数。

2 6
2 3
3 4

9 3

拿三件重 2、价值 3 的物品，正好重 $2 \times 3 = 6$ ，总价值 $3 \times 3 = 9$ ，是最大值；其它装法价值都更低，所以最多件数就是 3。

$1 \leq n \leq 50$ ， $0 \leq V \leq 2000$ ， $1 \leq w_{i} \leq 1 0^{9}$ ， $1 \leq v_{i} \leq 1 0^{9}$ ，答案不超过 $1 0^{18}$ 。