问题

(01)分数规划是用来解决这样一类问题

有(n)个物品，每个物品都有一个属性(p)和(w)。要从中选出(k)个物品使得(frac{sumlimits_{i=1}^kp_i}{sumlimits_{i=1}^kw_i})最大，输出最大值。要求是个分数

思想

首先二分一个答案(x)。
然后将上面的问题转化为要选(k)个物品使得[frac{sumlimits_{i=1}^kp_i}{sumlimits_{i=1}^kw_i} geq x]
即[sumlimits_{i=1}^kp_i-sumlimits_{i=1}^kw_itimes x ge 0]
即[sumlimits_{i=1}^k{p_i-w_i times x} ge 0]
所以对于每个物品，按照上面这个式子排个序。看最大的k个是否满足条件即可。如果满足条件就统计出答案。

例题

51nod 1257

代码

/* * @author: wxyww * @date:   2019-02-09 08:30:09 * @last modified time: 2019-02-09 09:00:36 */ #include<algorithm> #include<cstring> #include<cstdio> #include<iostream> #include<cstdlib> #include<cmath> #include<ctime> #include<bitset> using namespace std; typedef long long ll; const int n = 50000 + 10; const double eps = 1e-9; ll read() {     ll x=0,f=1;char c=getchar();     while(c<'0'||c>'9') {         if(c=='-') f=-1;         c=getchar();     }     while(c>='0'&&c<='9') {         x=x*10+c-'0';         c=getchar();     }     return x*f; } struct node {     int w,p;     double x; }a[n]; bool tmp(node x,node y) {     return x.x > y.x; } int n,k; int check(double w,int &x,int &y) {     for(int i = 1;i <= n;++i)         a[i].x = double(a[i].w) - double(a[i].p * w);     sort(a + 1,a + n + 1,tmp);     double ans = 0;     for(int i = 1;i <= k;++i) ans += a[i].x;     if(ans >= 0) {         x = 0,y = 0;         for(int i = 1;i <= k;++i) {             x += a[i].w;             y += a[i].p;         }         int g = __gcd(x,y);         x /= g; y /= g;         return 1;     }     return 0; } int main() {     n = read();     k = read();     double r = 0;     for(int i = 1;i <= n;++i) a[i].p = read(),a[i].w = read(),r = max(r,(double)a[i].w);     double l = 0;     int x,y;     while(r - l > eps) {         double mid = (l + r) / 2;         if(check(mid,x,y)) l = mid;         else r = mid;     }     printf("%d/%dn",x,y);     return 0; }