題意：n個物品，價值v,重量wi,選k個，平均價值最大

樣例

3 2(n,m)

2 2(w,v)

5 3

2 1

0.75

分析：看到這道題的一瞬間，我就有了一個zz想法，貪心搞啊，但是試了一發(fā)樣例，發(fā)現(xiàn)掛了? (3+2)/(2+5)=0.714，? 最佳是第一個和第三個，這就尷尬了，發(fā)現(xiàn)不僅和平均價值相關(guān)，

而且和重量相關(guān)，比如樣例，雖然 5 3的平均價值比2 1大，但是重量的增加反而拉低了平均價值，最后參考了一發(fā)挑戰(zhàn)程序設(shè)計的想法，二分

二分平均質(zhì)量?? ∑_i€s vi/∑wi>=mid,然后變形 ?∑_i€s(vi-x*wi)>=0，然后排序貪心搞就ok了

轉(zhuǎn)載于:https://www.cnblogs.com/jihe/p/5532522.html

總結(jié)

以上是生活随笔為你收集整理的最大化平均值的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。