最大化平均值问题

题意

n个物品，有体积和价值里拿k个，问怎么样拿，k个物品的平均价值(总价值/总体积)最大。

笺释

如果按照价值/体积排序，贪心选取之后并不能保证最后的总平均价值最大。

转化为不等式就是

a+w1/b+v1>a+w2/b+v2

w1/v1>w2/v2 并不能保证上述不等式成立。

这让我想起了，那个题之所以能拿就拿是因为最终要最优化的是全部价值之和，就等于是用密度不同的物质去填满一定体积的球，那肯定是能用密度大的就用密度大的了。

而这道题的话，我们二分价值，只需要确定n个物品里选k个能否达到这个平均价值即可，如果能，平均价值变大，否则变小。

而在确定了价值x的基础上可以对n个物品进行排序。

因为最终要确定的是sum(v)/sum(w)>=x,也就是sumv>=sum(w)*x,对于求和来说，可以将x放入求和号内，最终确定只要v-w*x大的就一定选。按照v-w*x排序后。选前k个就好了。

完整代码

#include
    
     #define MAXN 1005#define INF 0x3f3f3f3ftypedef long long ll;using namespace std;int n,k;double x;struct node{    double w,v;}nodes[MAXN];bool cmp(node n1,node n2){    return n1.v-n1.w*x>n2.v-n2.w*x;}int check(){    sort(nodes+1,nodes+1+n,cmp);    double ans1=0,ans2=0;    for(int i=1;i<=k;i++)    {        ans1+=nodes[i].v;        ans2+=nodes[i].w;     //   printf("B %f %f\n",nodes[i].v,nodes[i].w);    }   // printf("%f %f\n",ans1,ans2);    if(ans1/ans2>=x)    {        return 1;    }    else    {        return 0;    }}int main(){    scanf("%d %d",&n,&k);    double l=INF;    double r=0;    for(int i=1;i<=n;i++)    {        scanf("%lf %lf",&nodes[i].w,&nodes[i].v);       // printf("C %f %f\n",nodes[i].v,nodes[i].w);        l=min(l,nodes[i].v/nodes[i].w);        r=max(r,nodes[i].v/nodes[i].w);    }    int flag=0;    while(l<=r)    {        flag++;        if(flag>100)        {            break;        }        x=(l+r)/2;        if(check())        {            l=x;        }        else        {            r=x;        }    }    printf("%f\n",l);}