可分割背包问题

题目描述

有个贪婪的冒险家来到一个神秘的山洞，他发现里面有很多的财宝，他都想把这些财宝带走，但是他只有一个背包，而且背包的容量是有限的。但他贪婪的本性告诉他，要用这个背包尽可能装满，使得这个背包里财宝的价值最高。所有的财宝都是可以分割成一个单位装进背包里的。

输入格式

第一行两个整数n和g，分别表示财宝的种类数量和背包的容量。接下来n行，每行两个整数a和b，分别表示第i种财宝的数量和价值。

输出格式

输出一个数，就是背包所能装的财宝的最大价值，结果保留2位小数。

样例输入 #1

5 10
5 5
4 8
3 12
10 30
2 15

样例输出 #1

42.00

数据范围

0<n<100, 0<g<10000

知识点与难度

本题涉及的知识点从属于 GESP 5级（贪心基础），难度等级：⭐⭐。

测试点分布