问题 5840 --背包问题(二)

5840: 背包问题(二)

题目描述

给定 $n$ 个物品,每个物品的价值为 $v_i$,重量为 $w_i$,请从这些物品中选出一些,在它们的重量之和不超过一个给定值 $c$ 的前提下,价值之和达到最大。 注意本题中物品的重量可能比较大。

输入

第一行:两个整数 $n$ 与 $c$。 第二行到第 $n+1$ 行,第 $i+1$ 行有两个整数表示 $v_i$ 与 $w_i$

输出

单个整数:表示满足限定条件下的最大价值和。

样例输入输出

输入#1 复制
3 1000
90 900
53 550
38 400
输出#1 复制
91

提示

+ 对于 $30\%$ 的数据, $n\leq 20$; + 对于 $60\%$ 的数据, $c\leq 10000$; + 对于 $100\%$ 的数据, $1\leq n\leq 500$,$1\leq c\leq 10^{18}$,$1\leq v_i\leq 500$,$1\leq w_i\leq 10^{18}$。 样例1说明:选后两个物品
序号 标题 作者 发表时间 费用 订购数 操作