changed 3 years ago  
Published Linked with GitHub

最大化平均值

目標:有n個物品可以選，每個物品都有價格v跟重量w，你要購買k個物品，價值為價格總和除以重量總和，求最大的價值為?

可以用二分搜尋找到最接近的數值(二分搜答案): x

式子1. \[\dfrac{∑v[i]}{∑w[i]}>=x\]
式子2. \[∑v[i]>=∑(x*w[i])\]
式子3. \[∑(v[i]-x*w[i])>=0\]

因此我們就可以利用式子3二分搜答案，如果成立的時候，代表最大值比x大，往比較大的去搜尋，否則往小的搜尋，直到誤差值小於EXP。





















bool check(float x){
    for(int i=0;i<n;i++){
        cache[i]=weight[i]-x*price[i];
    }
    sort(cache,cache+n,greater<float>());
    float sum=0;
    for(int i=0;i<k;i++){
        sum+=cache[i];
    }
    return sum >= 0;
}

while (R - L > 0.0001){
    double m = (L + R) / 2;
    if (check(m)){
        L = m;
    } else {
        R = m;
    }
}
Select a repo