二分法求最大化平均值

版权声明：转载请注明出处。 https://blog.csdn.net/u014427196/article/details/46380489

有n个物品，每个物品分别对应一个重量和价值。要求选出k个，使得平均每单位重量的价值最大。

思路：

设k的集合是S ，使得平均值最大，即 Vs/Ws 最大。枚举答案x，Vs/Ws>=x，即 Vs – Ws*x>=0 成立。二分x即可。

代码：

#include <stdio.h>
#include <iostream>
#include <string.h>
#include <algorithm>
#include <math.h>
#include <ctype.h>
#include <time.h>
#include <queue>
#include <iterator>
#include <vector>
#include <set>

using namespace std;

const int MAXN = 100000;
const double INF = 1e9;
int n, k;

struct node
{
    double w;
    double v;   
}p[MAXN];

bool cmp2(double a, double b)
{
    return a > b;
}

double tmp[MAXN];

int c(double x)
{
    for (int i = 0; i < n; i++)
    {
        tmp[i] = p[i].v - x*p[i].w;
    }
    sort(tmp,tmp+n,cmp2);
    double sum = 0;
    for (int i = 0; i < k; i++)
        sum += tmp[i];
    if (sum >= 0) return 1;
    return 0;
}

void solve()
{
    double down = 0, up = INF;
    for (int i = 0; i < 100; i++)
    {
        double mid = (up + down)/2;
        if (c(mid)) down = mid;
        else up = mid;
    }
    printf("%.3lf",down);
}

int main()
{
    while (cin >> n >> k)
    {
        for (int i = 0; i<n; i++)
            cin >> p[i].w >> p[i].v;
        solve();
    }
    return 0;   
}