編程之美第一篇 01分數規劃

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

轉載請附上地址：

http://www.cnblogs.com/handsomecui