最大化平均值

有n个物品的重量和价值分别是Wi和Vi，从中选出K个物品使得单位重量的价值最大。

最大化平均值的经典，一般最先想到可能的方法是按照单位价值排序，从大到小的进行选取，但是这个方法对于下面一组例子来说：

n=3;  k=2;   (w,v)=(2,2),(5,3),(2,1);则可能得出的结果是5/7=0.714，所以这个方法是要排除的，那么如何想到最大化平均值这个方向呢?实际上，对于这个问题我们可以使用二分搜索法解决，我们定义：

条件get(mid):=可以选择使得单位重量的价值不小于mid

因此，原问题就变成了求满足get(mid)的最大mid，那么如何判断get(mid)是否可行？假设我们选了某个物品的集合S（）那么它们的单位重量的价值是;定义sum(v)为v的值的和

sum(Vi(i属于S))/sum(Wi(i属于S))；因此就变成了判断是否存在mid满足以下条件：sum(Vi(i属于S))/sum(Wi(i属于S))>=mid;变形得到：sum(Vi-mid*Wi)>=0，因此对此式的值进行贪心选取，进一步求sum(Vi-mid*Wi)从大到小排列中前k个的和不小于零，每次判断的复杂度为O(n*log(n))

实现：

登录后复制

      
      

       
       //输入
       
       

       
       int 
       
       n,
       
       k;
       
       

       
       int 
       
       v[
       
       max_n],
       
       w[
       
       max_n];
       
       

       
       double 
       
       y[
       
       max_n];
       
       

       
       bool 
       
       get(
       
       double 
       
       mid)
       
       
{
       
       
    
       
       bool 
       
       ok;
       
       
    
       
       for(
       
       int 
       
       i
       
       =
       
       0;
       
       i
       
       <
       
       n;
       
       i
       
       ++){
       
       
    
       
       y[
       
       i]
       
       =
       
       v[
       
       i]
       
       -
       
       mid
       
       *
       
       w[
       
       i];
       
       
    }
       
       
    
       
       sort(
       
       y,
       
       y
       
       +
       
       n);
       
       
    
       
       //计算从大到小前k个数的和
       
       
    
       
       double 
       
       sum
       
       =
       
       0;
       
       
    
       
       for(
       
       int 
       
       i
       
       =
       
       0;
       
       i
       
       <
       
       k;
       
       i
       
       ++){
       
       
    
       
       sum
       
       +=
       
       y[
       
       n
       
       -
       
       i
       
       -
       
       1];
       
       
    }
       
       
    
       
       if(
       
       sum
       
       >=
       
       0) 
       
       ok
       
       =
       
       true;
       
       
    
       
       else 
       
       ok
       
       =
       
       false;
       
       
    
       
       return 
       
       ok;
       
       
}
       
       

       
       void 
       
       binsearch()
       
       
{
       
       
    
       
       double 
       
       ll
       
       =
       
       0,
       
       rr
       
       =
       
       inf;
       
       
    
       
       while(
       
       fabs(
       
       ll
       
       -
       
       rr)
       
       >
       
       eps)
       
       
    {
       
       
        
       
       double 
       
       mid
       
       =(
       
       ll
       
       +
       
       rr)
       
       /
       
       2;
       
       
        
       
       if(
       
       get(
       
       mid)) 
       
       ll
       
       =
       
       mid;
       
       
        
       
       else 
       
       rr
       
       =
       
       mid;
       
       
    }
       
       
    
       
       printf(
       
       "%.2f\n",
       
       rr);
       
       
}
      
      
      
      

       
       
1.
       
       
2.
       
       
3.
       
       
4.
       
       
5.
       
       
6.
       
       
7.
       
       
8.
       
       
9.
       
       
10.
       
       
11.
       
       
12.
       
       
13.
       
       
14.
       
       
15.
       
       
16.
       
       
17.
       
       
18.
       
       
19.
       
       
20.
       
       
21.
       
       
22.
       
       
23.
       
       
24.
       
       
25.
       
       
26.
       
       
27.
       
       
28.
       
       
29.
       
       
30.
       
       
31.