最大化平均值

题意:n个物品,价值v,重量wi,选k个,平均价值最大

样例

3 2(n,m)

2 2(w,v)

5 3

2 1

0.75

分析:看到这道题的一瞬间,我就有了一个zz想法,贪心搞啊,但是试了一发样例,发现挂了  (3+2)/(2+5)=0.714,  最佳是第一个和第三个,这就尴尬了,发现不仅和平均价值相关,

而且和重量相关,比如样例,虽然 5 3的平均价值比2 1大,但是重量的增加反而拉低了平均价值,最后参考了一发挑战程序设计的想法,二分

二分平均质量   ∑i€s vi/∑wi>=mid,然后变形  ∑i€s(vi-x*wi)>=0,然后排序贪心搞就ok了

原文地址:https://www.cnblogs.com/jihe/p/5532522.html