g6-08028. 同重包裹 · 林老师的题库

题目描述

小杨有一批重量完全相同的物品：共 $n$ 件，每件都重 $w$ ，第 $i$ 件价值 $v_{i}$ ，每件只有一件，最多选一次，背包容量为 $V$ 。求最大总价值；第一行输出它，第二行输出「YES」，表示按价值从高到低能装就装的装法恰好也能得到这个最大值。

第一行三个整数 $n, w, V$ 。

第二行 $n$ 个整数 $v_{i}$ 。

两行：第一行最大总价值，第二行 YES。

4 3 9
10 20 30 40

90
YES

容量 9，装 3 件，取价值最大的 40+30+20=90。

$1 \leq n \leq 1000$ ， $1 \leq w \leq 100$ ， $1 \leq V \leq 1 0^{9}$ ， $1 \leq v_{i} \leq 1 0^{9}$ 。

提示：设最多装 $m = min (n, ⌊ V / w ⌋)$ 件，取价值最大的 $m$ 件求和；注意 64 位整数。