RYIP在线题库
首 页   >   习题练习   >   提交
Problem1399--可分割背包问题

1399: 可分割背包问题

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 128 MB

【 Description 】

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

【 Input 】

    第一行两个整数n和g,分别表示财宝的种类数量和背包的容量(单位升),其中 0 < n < 100,0 < g < 10000
接下来有n行,每行两个整数ai和bi,分别表示第i种财宝的数量(单位升)和价值

【 Output 】

    输出一个数,就是这个贪婪的冒险家的背包所能装的财宝的最大价值,结果保留2位小数

【 Sample Input 】

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

【 Sample Output 】

42.00

【HINT】

P2240 【深基12.例1】部分背包问题


【 Source/Category 】

TW 贪心