问题
(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个是否满足条件即可。如果满足条件就统计出答案。
例题
代码
/*
* @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;
}内容来源于网络如有侵权请私信删除
- 还没有人评论，欢迎说说您的想法！
客服
