NOJ上机系统 准备中……
载人航天是人类探索太空的重要方式之一。载人航天的目的是将宇航员送入太空，进行科学实验、技术验证、空间站建设等任务。载人航天的发展历程可以追溯到20世纪50年代，当时苏联和美国开始了载人航天的竞赛。1961年，苏联宇航员加加林成功地进行了第一次载人航天飞行。1969年，美国宇航员阿姆斯特朗成功地登上了月球。自此之后，载人航天技术不断发展，人类在太空中进行了大量的科学实验和技术验证。
为了尽可能的的延长宇航员在太空中的停留时间，食物是必不可少的，但是飞船的容量有限，仅能装载一部分食物箱上去。现在，宇航局握有所有食物箱的卡路里和质量，你需要帮助宇航局选择出一部分食物箱，使得它们的总质量不超过飞船的承载能力，同时总卡路里最大。
第一行两个整数 $$$n$$$ 和 $$$m$$$，表示食物箱的数量和飞船的承载能力。题目保证，$$$1 \leq n \leq 100$$$， $$$1 \leq m \leq 1000$$$。
接下来 $$$n$$$ 行，每行两个整数 $$$w_i$$$ 和 $$$v_i$$$，表示第 $$$i$$$ 个食物箱的质量和卡路里。题目保证，$$$1 \leq w_i, v_i \leq 100$$$。
输出一行一个整数，表示能够带上飞船的食物箱的最大总卡路里。
3 70 71 100 69 1 1 2
3
4 1 3 5 2 7 4 11 9 2
0
5 25 1 1 1 2 1 3 1 4 1 5
15
在第一组样例中，由于总负载不超过 $$$70$$$ ，所以可以选择第2和第3个食物箱，总卡路里为 $$$1+2=3$$$ 。
题目保证，对于 $$$20\%$$$ 的数据点，$$$(\sum_{i=1}^{n} w_i) \leq m$$$。
题目保证，对于 $$$20\%$$$ 的数据点，$$$n \leq 3$$$（类似样例1）。
题目保证，对于 $$$60\%$$$ 的数据点，数据中每一个食物箱的质量 $$$w_i$$$ 都是相同的（类似样例3）。
题目保证，对于 $$$100\%$$$ 的数据点，$$$1 \leq w_i, v_i \leq 100$$$，$$$1 \leq n \leq 100$$$， $$$1 \leq m \leq 1000$$$。
信息
提供者 机考平台
代码 PROB1034
标签
提交 1019
通过 428
通过率 42%
修改日期 2025-03-24 16:03:47
相关题目