題目描述：

有n個物品的重量和價值分別為Wi和Vi。從中選出k個物品使得單位重量的價值最大。

例如：
n=3
k=2
(w,v)={(2,2) , (5,3) , (2,1) }

輸出應為0.75

分析：
一般我們最先想到的就是把物品按照單位價值進行排序，從大到小貪心的進行選取。但是這種方法對于樣例的輸出應該為5/7=0.714，所以這個方法是不行的。

這個問題應該使用二分搜索法解決，定義：
C(x)，表示，可以選擇的單位重量的價值不小于x

我們要求滿足C（x）的最大的x，

單位重量的價值為：Vi / Wi

Vi / Wi>=x.

即C(x)=（Vi -x Wi），從大到小排序中的錢k個的和不小于0.

代碼：

#include<iostream> #include<stdio.h> #include<algorithm> using namespace std; int n,k; int w[10009],v[10009]; double y[10009]; bool cmp(double a,double b) {return a>b; } bool C(double x) {for(int i=0;i<n;i++)y[i]=v[i]-x*w[i];sort(y,y+n,cmp);double sum=0;for(int i=0;i<k;i++)sum+=y[i];return sum>=0; }void solve() {double lb=0,ub=0x3f3f3f3f;for(int i=0;i<100;i++){double mid=(lb+ub)/2;if(C(mid)) lb=mid;elseub=mid;}printf("%.2lf\n",ub); } int main() {scanf("%d%d",&n,&k);for(int i=0;i<n;i++)scanf("%d%d",&w[i],&v[i]);solve();return 0; }

轉載于:https://www.cnblogs.com/cmmdc/p/7207895.html

總結

以上是生活随笔為你收集整理的最大化平均值 （二分搜索法）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。