#P0034. 【模版】部分背包问题

【模版】部分背包问题

题目描述

未来教育的高材生小未走进了装满宝藏的藏宝洞。藏宝洞里面有 N(N≤100)N(N \le 100) 个金块,第 ii 个金块的总重量和总价值分别是 mim_i 和 viv_i (1≤mi,vi≤1001\le m_i,v_i \le 100)。小未有一个承重量为 T(T≤1000)T(T \le 1000) 的背包,但并不一定有办法将全部的金块都装进去。他想装走尽可能多价值的金块,但是金块的数量实在太多了,他数的眼都花了,于是想要你写个代码来帮他算一下。

需要注意的是,所有金块都可以随意分割,分割完的金块重量价值比(也就是单位价格)不变。

输入格式

第一行包含空格隔开的两个整数 N,TN,T,分别为金块的个数和背包的最大承重。

接下来 NN 行,这 NN 中的第 ii 行包含空格隔开的两个整数 mi,vim_i,v_i,分别为第 ii 个金块的总重量和总价值。

输出格式

输出一个实数,即可以获得的最高的金块总价值。注意,由于浮点数存在误差,只要您的答案与标准答案之间的误差不超过 10−610^{-6}, 您的答案就会被认为是正确的。

样例 #1

样例输入 #1

4 50
10 60
20 100
30 120
15 45

样例输出 #1

240.0000000000