POJ3757SimpleDistributedstoragesystem01分数规划

时空隧道

题意&＃xff1a;
给出n台机器&＃xff0c;选出k台来完成任务&＃xff0c;最小化fi*ci…
对于每个机器有三个属性p b c
每台机器完成任务的时间&＃61;f[i]/p[i]&＃43;f[i]/b[i]
要求每台机器完成任务时间相同…并且∑f[i]&＃61;F

分析&＃xff1a;
最优值问题…考虑转化为可行性问题…那不就是01分数规划么…
01分数规划详解&＃xff08;请自行出门右转&＃xff09;
怎么转化为基本模型呢…
先把信息列出来吧…
ans&＃61;∑f[i]*c[i]…
time&＃61;f[i]/p[i]&＃43;f[i]/b[i]—>f[i]&＃61;time*p[i]*b[i]/(p[i]&＃43;b[i])…
F&＃61;∑f[i]—>F&＃61;time*∑x[i] (x[i]&＃61;p[i]*b[i]/(p[i]&＃43;b[i]))…
time&＃61;F/∑x[i]…
ans&＃61;∑(x[i]*c[i]*F/∑x[i])…
然后就套模板好啦…

代码如下&＃xff1a;

#include
#include
#include
#include
//by NeighThorn
using namespace std;
const int maxn&＃61;20000&＃43;5;
int n,k;
double F,p[maxn],b[maxn],c[maxn],x[maxn],ans,mid;
struct M{double p,b,c,x;friend bool operator <(M a,M b){return F*a.x*a.c-mid*a.x}s[maxn];
inline bool check(void){sort(s&＃43;1,s&＃43;n&＃43;1);double sum&＃61;0;for(int i&＃61;1;i<&＃61;k;i&＃43;&＃43;)sum&＃43;&＃61;F*s[i].x*s[i].c-mid*s[i].x;if(sum>&＃61;0)return true;return false;
}
signed main(void){scanf("%d%d%lf",&n,&k,&F);for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;)scanf("%lf%lf%lf",&s[i].p,&s[i].b,&s[i].c),s[i].x&＃61;s[i].p*s[i].b/(s[i].p&＃43;s[i].b);double l&＃61;0,r&＃61;10000000000;while(r-l>&＃61;1e-6){mid&＃61;(l&＃43;r)/2.0;if(check())ans&＃61;mid,l&＃61;mid;elser&＃61;mid;}printf("%.4f\n",ans);return 0;
}

by >_