g6-07987. 值域·边界 · 林老师的题库

题目描述

小杨在收拾行李：有 $n$ 件物品，第 $i$ 件重 $w_{i}$ 、价值 $v_{i}$ ，行李箱容量为 $V$ （最多可达 $1 0^{9}$ ），每件只有一件，最多拿一次。数据里有很多 $v_{i} = 0$ 的物品，也有单件价值就超过 $V$ 的物品。求他能带走的最大总价值。

第一行两个整数 $n, V$ 。

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

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

3 100
1000000000 0
999999999 0
1 5

只有第 3 件有正价值且能装下。

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

提示：值域倒置时 $d p$ 数组大小为总价值 $+ 1$ ；全 0 价值时答案为 0。