POJ 2976 Dropping test（01分数规划模板）

01分数划分详情可阅读：http://www.cnblogs.com/perseawe/archive/2012/05/03/01fsgh.html

题意：

给出n个a和b，让选出n-k个使得最大

二分法：

#include<cstdio>

#include<iostream>

#include<queue>

#include<cstring>

#include<string>

#include<map>

#include<vector>

#include<algorithm>

#define rep(i,a,b) for(int i = a; i < b; i++)

#define _rep(i,a,b) for(int i = a; i <= b; i++)

using namespace std;

const int maxn =  + ;

const double inf = 1e9;

const double eps = 1e-;

double a[maxn] , b[maxn], d[maxn];

int n, k;

double check(double L){

    double sum = ;

    for(int i = ; i < n; i++) d[i] = a[i] - b[i] * L;

    sort(d,d+n);//由于都是可取的， 那么就取最大的k个， 使得F(L)尽量大

    rep(i,k,n) sum += d[i];

    return sum;

}

int main()

{

    while(~scanf("%d %d", &n, &k) && n){

        rep(i,,n)scanf("%lf", &a[i]);

        rep(i,,n)scanf("%lf", &b[i]);

        double L = inf, R = -inf, Mid;

        for(int i = ;i < n; i++){

            L = min(a[i]/b[i], L); //如果求某些分数分子分母分别相加和最大， 那么这个和肯定小于等于某个分数

            R = max(a[i]/b[i], R); //如果求某些分数分子分母分别相加和最小， 那么这个和肯定小于等于某个分数

        }

        while( R - L > eps){

            Mid = L + (R-L)/;

            if(check(Mid) > ) //检查这个L值是否使F(L) = sigma(a[i] - L*b[i]) * ki取值为0(ki是取的k个数)

                L = Mid;

            else

                R = Mid;

        }

        printf("%.0f\n", L * );

    }

    return ;

}

Dinkelbach

#include<cstdio>

#include<iostream>

#include<queue>

#include<cstring>

#include<string>

#include<map>

#include<vector>

#include<algorithm>

#include<cmath>

#define rep(i,a,b) for(int i = a; i < b; i++)

#define _rep(i,a,b) for(int i = a; i <= b; i++)

using namespace std;

const int maxn =  + ;

const double inf = 1e9;

const double eps = 1e-;

struct node{

    double a, b, d;

    bool operator <(const node& x ) const{

        return d < x.d;

    }

}arr[maxn];

int n, k;

double Dinkelbach()

{

    double L,ans=; //L一开始随机赋值

    double x,y;

    while(){

        L = ans;

        for(int i=;i<n;i++)

            arr[i].d = arr[i].a - L * arr[i].b;

        sort(arr, arr + n);

        x=y=;

        for(int i=k;i<n;i++){

            x+=arr[i].a;

            y+=arr[i].b;

        }

        ans=x/y;//保存结果

//        printf("%.16f\n", ans);

        if(abs(L-ans) < eps) return L;

    }

}

int main()

{

//    freopen("1.txt","r", stdin);

    while(~scanf("%d %d", &n, &k) && n){

        rep(i,,n)scanf("%lf", &arr[i].a);

        rep(i,,n)scanf("%lf", &arr[i].b);

        printf("%.0f\n", Dinkelbach()* );

    }

    return ;

}