题目描述
小王是一位勤劳的货车司机,最近他接到了一项任务,要在一天内尽可能多地运送一些货物。这些货物种类繁多,有的是大米,有的是面粉,甚至还有沙石和泥土等。由于货车的载重量有限,小王必须精心选择哪些货物值得优先运输,以在不超载的情况下最大化货物的总价值。
货车的核载重量为 C 吨,市场上有 M 种不同的货物,每种货物的重量和价值分别为 wi 吨和 vi 元。小王希望你能帮他计算,在不超过载重限制的前提下,货车装载的货物总价值最高能达到多少。
输入
第一行包含两个整数 M 和 C,分别表示可选货物的数量和货车的核载重量。
接下来的 M 行中,每行包含两个整数 wi 和 vi,分别表示第i种货物的重量和价值。
(M<10000,C<10000,0<wi≤100,0≤vi≤100)
输出
输出一个浮点数,表示货车能装载的最大货物总价值(保留一位小数)
样例输入
5 36
99 87
68 36
79 43
75 94
7 35
样例输出
71.3
(贪心算法)