问题1895--小数背包问题

1895: 小数背包问题

时间限制: 1 Sec  内存限制: 128 MB
提交: 17  解决: 10
[提交] [状态] [讨论版] [命题人:]

题目描述

有一个背包，背包容量是M(0<M≤500)，有N(1<N≤1000)个物品，物品可以分割成任意大小。要求尽可能让装入背包中的物品总价值最大，但不能超过总容量。

输入

第1行有两个数，M和N；
第2行到N+1行：第i行为第i-1个物品的价值和质量（均为小于100的正整数），中间用空格隔开。

输出

只有一个数为最大总价值（保留一位小数）。

样例输入 Copy 

150 7
10 35
40 30
30 60
50 50
35 40
40 10
30 25

样例输出 Copy 

190.6

来源/分类

入门组 贪心算法 
[提交] [状态]