如题，我们在区间$[p,r]$内寻找重量不小于 $T$ 的最优解，可先找到性价比 $f[p...r]$ 的中位数位置 $mid$，根据中位数对数组进行划分，使得$f_i\le f_j(1\le i\le mid< j\le r)$，然后统计$mid$右端，即性价比高于中位数的重量和 $W_R$ 与价值和 $V_R$。

• 若$W_R\ge T$，则 $T$ 可以仅右中位数右端的商品组合出最优解。
• 若$W_R< T$,显然中位数右端的商品需要全部被选择，并在左端寻找重量不小于 $T-W_R$ 的最优解。

于是我们每次将范围减少一半，而每次递归需要计算 $W_R$ 与 $V_R$ 并寻找中位数的位置，平均时间复杂度为 $\Theta(n)$。因此可以得到递归式：

根据主方法，该算法时间复杂度为$\Theta(n)$.

代码

#include<bits/stdc++.h>
using namespace std;
default_random_engine e;

template<typename T>
int myPartition(vector<T> &arr, int p, int r){
    T pivot=arr[r];
    int i=p-1;
    for(int j=p;j<r;++j) if(arr[j]<=pivot) swap(arr[++i],arr[j]);
    swap(arr[i+1],arr[r]);
    return i+1;
}

template<typename T>
int randomPartition(vector<T> &arr, int p, int r){
    uniform_int_distribution<int> d(p,r);
    int i=d(e);
    swap(arr[i],arr[r]);
    return myPartition(arr,p,r);
}

template<typename T>
int randomSelect(vector<T> &arr, int p, int r,int i){
    if(p==r) return p;
    int q=randomPartition(arr,p,r);
    int k=q-p+1;
    if(k==i) return q;
    else if(k>i) return randomSelect(arr,p,q-1,i);
    else return randomSelect(arr,q+1,r,i-k);
}

struct Good{
    double w;
    double v;
    double f;
    Good()=default;
    Good(double __w,double __v):w(__w),v(__v),f(v/w) {}
    void setVal(double __w, double __v){
        w=__w;v=__v;f=v/w;
    }
};
bool operator<=(Good const& lhs, Good const& rhs){
    return lhs.f<=rhs.f;
}

/* 部分背包问题 */
double fractionalKnapsack(vector<Good> &goods, int p, int r, double W){
    if(p==r){
        if(goods[p].w<=W) return goods[p].v;
        else return goods[p].f*W;
    }
    int mid=randomSelect(goods,p,r,(r-p+1)/2);
    double WR=0,VR=0;
    for(int i=mid+1;i<=r;++i) { WR+=goods[i].w; VR+=goods[i].v;}
    if(WR>=W) return fractionalKnapsack(goods,mid+1,r,W);
    else return fractionalKnapsack(goods,p,mid,W-WR)+VR;
}

int main(){
    ios_base::sync_with_stdio(false);
    int n;
    double W;
    cin>>n>>W;
    vector<Good> goods(n);
    for(int i=0;i<n;++i) {
        double w,v;
        cin>>w>>v;
        goods[i].setVal(w,v);
    }
    cout<<fixed<<setprecision(2)<<fractionalKnapsack(goods,0,n-1,W);
    return 0;
}