编程之美第一篇 01分数规划
jopen
9年前
01分数规划
01分数规划问题其实就是解决单价之类的问题，假设给你n个物品，让你找出选k个物品的最大单价；例如南阳oj：Yougth的最大化；解决这类问题可以用二分查找，这类问题跟二分极大化最小值，极小化最大值有一些相似的地方，均是从结果出发，来进行二分查找；例如上面南阳那道题，可以转化一下；
由于v/w=单价；所以v=w*单价；即v-w*单价=0；有了这个关系，我们马上可以想到二分来查找这个值；
那么我们可以定义一个 count 数组来记录 v-w* 单价的值；由于选 k 个只需要把 count 从大到小排下序就可以了；然后就是二分了；这类问题就是 01 分数规划问题；
代码实现：
#include<stdio.h> #include<algorithm> #define MAX(x,y) x>y?x:y using namespace std; const int MAXN=10010; struct Node{int v,w; }; Node res[MAXN]; double cont[MAXN]; int n,k; int fun(double mid){ for(int i=0;i<n;i++){ cont[i]=res[i].v-mid*res[i].w; } sort(cont,cont+n);double sum=0; for(int i=n-1;i>=n-k;i--)sum+=cont[i]; //printf("%lf\n",mid); return sum>=0?1:0; } double abs(double x){ return x>0?x:-x; } double search(double max){ double left=0,right=max,mid; while(right-left>1e-10){mid=(left+right)/2; if(fun(mid))left=mid; else right=mid; } return mid; } int main(){ while(~scanf("%d%d",&n,&k)){double max=0; for(int i=0;i<n;i++){ scanf("%d%d",&res[i].w,&res[i].v); max=MAX(max,res[i].v*1.0/res[i].w);// } printf("%.2f\n",search(max)); } return 0; } 与这个题相似的还有 poj Dropping tests；这个题意是：
给你n个数，让求删除k个数后
的最大值；
跟南阳那个题很相似，只需要找 n-k 个数即可；
代码实现：
#include<cstdio> #include<iostream> #include<algorithm> #include<cstring> #include<cmath> using namespace std; const int MAXN=10010; struct Node{ int a,b; }; Node dt[MAXN]; double d[MAXN]; int n,k; bool fsgh(double R){ double sum=0; for(int i=0;i<n;i++)d[i]=dt[i].a-R*dt[i].b; sort(d,d+n); for(int i=n-1;i>=n-k;i--)sum+=d[i]; return sum>0?true:false; } double erfen(double l,double r){ double mid; while(r-l>1e-6){ mid=(l+r)/2; if(fsgh(mid))l=mid; else r=mid; } return mid; } int main(){ while(scanf("%d%d",&n,&k),n|k){ double mx=0; k=n-k; for(int i=0;i<n;i++)scanf("%d",&dt[i].a); for(int i=0;i<n;i++)scanf("%d",&dt[i].b),mx=max(1.0*dt[i].a/dt[i].b,mx); printf("%.0f\n",erfen(0,mx)*100); } return 0; } 另外 01 分数规划还可以与图论结合在一起；例如：
和最小生成树结合在一起让你求一棵最优比率生成树；例如 poj Desert King；
题意：有 N 个村庄，给出每个村庄的坐标和海拔 , ， benifit 为两点之间的距离， cost 为两点的高度差，现在要求一棵树使得 cost / benift 最小 ；
咋一看跟 01 分数规划还真像，但是让求的是一棵树，我们该怎么办？其实就是求一个最小生成树罢了，最小生成树里面的 low 数组代表的是啥？权值！那直接把 low 数组里面的值换成 cost-benift*R 就好了，然后就是一个二分问题了；
代码实现：
#include<cstdio> #include<iostream> #include<cstring> #include<cmath> #include<algorithm> #define mem(x,y) memset(x,y,sizeof(x)) using namespace std; const int INF=0x3f3f3f3f; typedef long long LL; const int MAXN=1010; double vis[MAXN],low[MAXN]; int N; double R; struct Node{ double x,y,h; }; Node dt[MAXN]; double len[MAXN][MAXN],cost[MAXN][MAXN]; double getl(Node a,Node b){ double x=b.x-a.x,y=b.y-a.y; return sqrt(x*x+y*y); } bool prime(){ double total; mem(vis,0); for(int i=0;i<N;i++)low[i]=cost[0][i]-R*len[0][i]; total=0; vis[0]=1;// for(int i=0;i<N;i++){ double temp=INF; int k; for(int j=0;j<N;j++) if(!vis[j]&&low[j]<temp)temp=low[j],k=j; if(temp==INF)break; total+=temp; vis[k]=1; for(int j=0;j<N;j++) if(!vis[j]&&low[j]>cost[k][j]-R*len[k][j])low[j]=cost[k][j]-R*len[k][j]; } //printf("total=%lf R=%lf\n",total,R); if(total>0)return true; else return false; } int main(){ while(scanf("%d",&N),N){ mem(len,INF); mem(cost,INF); double mxl=-INF,mil=INF,mxc=-INF,mic=INF; for(int i=0;i<N;i++) scanf("%lf%lf%lf",&dt[i].x,&dt[i].y,&dt[i].h); for(int i=0;i<N;i++){ for(int j=i+1;j<N;j++){ len[j][i]=len[i][j]=getl(dt[i],dt[j]); cost[j][i]=cost[i][j]=abs(dt[i].h-dt[j].h); mxl=max(mxl,len[i][j]); mxc=max(mxc,cost[i][j]); mil=min(mil,len[i][j]); mic=min(mic,cost[i][j]); } } //printf("%lf %lf %lf %lf\n",mil,mic,mxl,mxc); double l=mic/mxl,r=mxc/mil; // printf("%lf %lf\n",l,r); while(r-l>1e-4){ R=(l+r)/2; if(prime())l=R; else r=R; } printf("%.3f\n",l); } return 0; } 另外 01 分数规划还可以与最短路结合在一起；求一个最优比率环；例如 poj Sightseeing Cows;
题意：这个人带牛旅行，旅行每个城市会有幸福度，通过每个城市会花费时间，让找平均每秒的最大幸福度；
注意这题是让求最大的，好像我们前面讲的都是最小的，那该怎么办呐？很简单以前是 hp-R*t; 转成 R*t-hp 不就好了吗？照样转化成最短路问题；但是可能产生负边啊；对了就是负边，二分就是从负边出发的，有负边证明 t 太大，没有 t 小，这就是二分的一个条件；由于负边我们可以用 bellman ，或者邻接表解决；
代码实现：
#include<cstdio> #include<iostream> #include<cstring> #include<cmath> #include<algorithm> #include<queue> #define mem(x,y) memset(x,y,sizeof(x)) using namespace std; const int INF=10000000000000; typedef long long LL; const int MAXN=1010; const int MAXM=100010; /*struct Node{ int u,v; double t; }; Node dt[MAXM];*/ struct Edge{ int from,to,next,t; }; Edge edg[MAXM]; int head[MAXM]; int edgnum; void add(int u,int v,int t){ Edge E={u,v,head[u],t}; edg[edgnum]=E; head[u]=edgnum++; } int L,P; double hp[MAXN],dis[MAXN]; int usd[MAXN],vis[MAXN]; /*void add(int u,int v,double t){ Node E={u,v,t}; dt[edgnum++]=E; }*/ //double R; /*bool Bellman(){ mem(dis,INF); mem(usd,0); dis[1]=0; while(1){ int temp=0; for(int j=0;j<edgnum;j++){ int u=dt[j].u,v=dt[j].v; double t=dt[j].t; //dis[v]=min(dis[v],dis[u]+R*t-hp[u]);//应该是R*t-hp[u]; if(dis[v]>dis[u]+R*t-hp[u])usd[v]++,dis[v]=dis[u]+R*t-hp[u],temp=1; if(usd[v]>L)return false; } if(!temp)return true; } }*/ bool SPFA(double R){ queue<int>dl; while(!dl.empty())dl.pop(); for(int i=1;i<=L;i++){ dis[i]=INF; vis[i]=0; usd[i]=0; } dl.push(1); vis[1]=1; usd[1]++; dis[1]=0; while(!dl.empty()){ int u=dl.front(); dl.pop(); vis[u]=0; for(int i=head[u];i!=-1;i=edg[i].next){ int v=edg[i].to,t=edg[i].t; if(dis[v]>dis[u]+R*t-hp[u]){ dis[v]=dis[u]+R*t-hp[u]; if(!vis[v]){ vis[v]=1; usd[v]++; dl.push(v); // printf("%d\n",usd[v]); if(usd[v]>=L)return false; } } } } return true; } int main(){ int a,b; int c; while(~scanf("%d%d",&L,&P)){ edgnum=0; double mih=INF,mxh=-INF; int mit=INF,mxt=-INF; mem(head,-1); for(int i=1;i<=L;i++){ scanf("%lf",hp+i); mih=min(mih,hp[i]); mxh=max(mxh,hp[i]); } while(P--){ scanf("%d%d%d",&a,&b,&c); add(a,b,c); mit=min(mit,c); mxt=max(mxt,c); } double l=mih/mxt,r=mxh/mit; // printf("%f %f\n",l,r); double R; while(r-l>=0.001){ R=(l+r)/2; if(SPFA(R))r=R; else l=R; } printf("%.2f\n",l); } return 0; } 01 分数规划是一个基本而且有用的算法，可以与图论连用，也可以与数据结构一起用；
上面提到的题解详情请见：
http://www.cnblogs.com/handsomecui/p/4690691.html
http://www.cnblogs.com/handsomecui/p/4971467.html
http://www.cnblogs.com/handsomecui/p/4972701.html
http://www.cnblogs.com/handsomecui/p/4973041.html
转载请附上地址：