分数规划问题

//分数规划 
//求形如 sigma(a[i])*w/sigma(b[i])*w  的极值
//这里w取值为0或1,代表这一项选或不选 

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e5+10;
int n,k;
ll s[N],c[N];

bool check(double mid){ //原比值等式最大值能不能>=ans 
    double res=0;
    vector<double>v;
    for(int i=1;i<=n;i++){
        v.push_back(s[i]*c[i]-mid*s[i]);
    }
    sort(v.begin(),v.end(),greater<double>());
    for(int i=0;i<n-k;i++){
        res+=v[i];
    }
    for(int i=n-k;i<n;i++){
        if(v[i]<0) break;
        res+=v[i];
    }
    return res>=0;
}

int main(){
    cin>>n>>k;
    for(int i=1;i<=n;i++){
        cin>>s[i];
    }
    for(int i=1;i<=n;i++){
        cin>>c[i];
    }
    double l=0,r=1e9;
    double ans=0;
    while(r-l>1e-10){
        double mid=(l+r)/2;  //枚举ans
        if(check(mid)) ans=mid,l=mid;
        else r=mid;
    }
    printf("%8f\n",ans);
    return 0;
} 

 

上一篇:【android】使用SharedPreferences存取复杂数据


下一篇:这不是TNT:py挂机脚本