货轮最优装载

题目描述

一艘货轮即将启航。港口有 N 个煤堆，第 i 个煤堆的总重量为 m_i 吨，总价值为 v_i 元。货轮的最大载重量为 T 吨。由于时间和空间限制，可能无法将全部煤堆都装上船。好在煤是散装货物，可以从任何一个煤堆中装载任意比例的煤（例如，装载某个煤堆的 40%）。如果装载了某个煤堆的 p 比例（0 <= p <= 1），那么装载的重量是 p * m_i 吨，获得的价值是 p * v_i 元。作为船长，你需要制定一个装载方案，在满足总装载重量不超过货轮载重量 T 的前提下，使得此次航行装载的货物总价值最大。

输入格式

第一行包含两个整数 N 和 T，分别表示煤堆的数量和货轮的最大载重量（单位：吨）。

接下来 N 行，每行包含两个整数 m_i 和 v_i，分别表示第 i 个煤堆的总重量（吨）和对应的总价值（元）。

输出格式

输出一行一个浮点数，表示在最优装载方案下能获得的最大总价值。结果需要精确到小数点后两位。

样例

输入：

4 60
20 100
30 120
10 60
25 80

输出：

280.00

数据范围

• 对于 30% 的测试数据，1 <= N <= 10，1 <= T <= 1000，1 <= m_i, v_i <= 1000。
• 对于 60% 的测试数据，1 <= N <= 100，1 <= T <= 10^4，1 <= m_i, v_i <= 10^4。
• 对于 100% 的测试数据，1 <= N <= 10^3，1 <= T <= 10^5，1 <= m_i, v_i <= 10^5。

提示：本题为分数背包问题，可按单位重量价值从高到低贪心装载。