A30746.【动态规划】【背包】小飞侠的游园方案
普及-
官方
通过率:0%
时间限制:1.00s
内存限制:128MB
题目描述
小飞侠星期天会邀他的灵儿妹妹到公园去玩。公园里有很多娱乐项目,可并不是每一项他们都喜欢,所以他们对每一项都进行了“喜欢度”的评分。因为小飞侠也是一个了不起的角色,所以他一定会选择在有限时间内的最好的方案。现在要你做的就是找出在规定时间内他们选择哪几项不同的活动可以使其“喜欢度”之和达到最大。
输入格式
第一行一个正整数N(1<=N<=100)表示总共的娱乐项目数。
第二行一个正整数表示规定的时间t(0<t<1000)。
下面有N行,其中第i+2行有两个正整数fi(0<=fi<=100)和ti(0<ti<=100),分别表示对项目i的“喜欢度”和它所耗费的时间。
输出格式
第一行输出最大的“喜欢度”之和。
输入输出样例
输入#1
3 5 1 2 5 5 4 3
输出#1
5