#P0034. 【模版】部分背包问题
【模版】部分背包问题
题目描述
未来教育的高材生小未走进了装满宝藏的藏宝洞。藏宝洞里面有 个金块,第 个金块的总重量和总价值分别是 和 ()。小未有一个承重量为 的背包,但并不一定有办法将全部的金块都装进去。他想装走尽可能多价值的金块,但是金块的数量实在太多了,他数的眼都花了,于是想要你写个代码来帮他算一下。
需要注意的是,所有金块都可以随意分割,分割完的金块重量价值比(也就是单位价格)不变。
输入格式
第一行包含空格隔开的两个整数 ,分别为金块的个数和背包的最大承重。
接下来 行,这 中的第 行包含空格隔开的两个整数 ,分别为第 个金块的总重量和总价值。
输出格式
输出一个实数,即可以获得的最高的金块总价值。注意,由于浮点数存在误差,只要您的答案与标准答案之间的误差不超过 , 您的答案就会被认为是正确的。
样例 #1
样例输入 #1
4 50
10 60
20 100
30 120
15 45
样例输出 #1
240.0000000000