01整数规划-白红宇

01整数规划

阅读量：4597 次

发布时间：2019-06-09

本文共 5586 字，大约阅读时间需要 18 分钟。

下面的不是很清楚，这个比较好。

简介：

详情前参见国家集训队论文 2007年胡伯涛论文

题意:求存在一个环路,所有的点权之和/所以的边权之和最大是多少？

http://poj.org/problem?id=3621

算法:此题是对01分数规划的应用,那么首先明白01分数规划的思想.

01分数规划的思想的描述如下：令c=(c1,c2,…,cn)和d=(d1,d2,…,dn)为n维整数向量，那么一个0-1分数规划问题用公式描述如下:FP: 最小化(c1x1+…cnxn)/(d1x1…dnxn)=cx/dx xi∈{0,1}这里x表示列向量(x1,x2,…,xn)T .0-1值向量的子集Ω称作可行域，而x则是Ω的一个元素，我们称x为可行解。即可以简化为y=c/d.那么再演变一下：y-c/d=0.我们目标是求y.那么我们可以假设函数f(y)=y-c/d.

重要结论:

对于分数规划问题，有许多算法都能利用下面的线性目标函数解决问题。

Q(L): 最小化 cx-Ldx xi∈{0,1}

记z(L)为Q(L)的最值。令x*为分数规划的最优解，并且令L*=(cx*)/(dx*)(注：分数规划的最值)。那么下面就容易知道了：

z(L) > 0 当且仅当 L<L*

z(L) = 0 当且仅当 L=L*

z(L) < 0 当且仅当 L>L*

此外，Q(L*)的最优解也能使分数规划最优化。因此，解决分数规划问题在本质上等同于寻找L=L*使z(L)=0

因此,求解f(y)=0,为其函数的最优解，即可以利用二分的思想逐步推演y,从而求得最优解.

回到题目,我们知道是求解segma(f[V])/segma(E[v])的最大值,同时每个结点对应一个点权,每条边对应一个边权,那么我们就可以联想到应用01分数规划的思想来求解.而01分数规划是与二分紧紧联系在一起的.那么怎么应用二分求解呢？

我们首先想想当仅仅有2个结点环路的时候,问题就演变为f(y)=y-c/d,而y是通过二分逐步推算出来的,那么我们的任务就变为在一定的精度范围内测试求解其最优解.当y-c/d>0时,y减少; y-c/d<0时,y增大.在2个结点之间,那么我们就可用重新将图的权变为y-c/d,这样问题就回到2个结点的环路是否存在负权回路,存在说明y-c/d<0,不存在y-c/d>0.从而进一步推算最优解y。

01整数规划问题，

01整数规划问题分为两类 最大化，最小化

以最小化如求最小值 l=ax/bx ，（ax bx是一些数的和），变形为 ax-l*bx=0,我们令 f(x)=min(ax-l*bx),我们要求的是这样的一个 l 对于给定的 l

首先 ax1-l*bx1=0

不存在 x 使得 (因为 l 是我们求的最小值)

ax-l*bx > 0

这样的话 ax>l*bx ;

关键是我们如何求这个l 呢? 有上面的我们可以得到，用二分法，求 l ，

对于 f(x)=min(ax-l*bx)

对于给定的 l

若 f(x)<0 则说明 l 偏大

若 f(x)>0 说明 l 偏小

对于图上的 01 整数规划我门只需要将边权变为 ax-l*bx 或者 l*bx- ax；

例如对于最优比率树：大意：给定一张图，每条边有一个收益值和一个花费值，求一个生成树，要求花费/收益最小，输出这个值

我们只需要将边权变为 a1-l*b1 然后求最小生成树就行判断求和的 ai-l*bi 的值于0 的大小

poj 2976 Dropping tests 【最优比例点】

View Code

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #include
          
            6 #include
           
             7 #include
             8 #define Min(a,b) a>b?b:a 9 #define Max(a,b) a>b?a:b10 #define CL(a,num) memset(a,num,sizeof(a));11 #define inf 999999912 #define maxn 103013 #define eps 1e-614 15 using namespace std;16 int cmp(const double a,const double b)17 {18 return a>b;19 }20 double a[maxn],b[maxn];21 double d[maxn];22 int main()23 {24 __int64 n,k,i;25 while(scanf("%I64d%I64d",&n,&k),n+k)26 {27 for(i=1;i<=n;i++)28 {29 scanf("%lf",&a[i]);30 }31 for(i=1;i<=n;i++)scanf("%lf",&b[i]);32 double l=0,r=-1;33 for(i=1;i<=n;i++)34 {35 if(a[i]/(b[i]*1.0)>r)r = a[i]/(b[i]*1.0);36 }37 38 int m=n-k;39 double ans,mid;40 r=100.0;41 while(r-l>eps)42 {43 mid=(l+r)/2;44 for(i=1;i<=n;i++)d[i]=a[i]*100.0-mid*b[i];45 sort(d+1,d+n+1,cmp);46 47 48 49 50 double temp=0;51 for(i=1;i<=m;i++)temp+=d[i];52 if(temp>=0)53 {54 55 56 57 58 l=mid;59 60 }61 else r=mid;62 }63 64 65 printf("%.0lf\n",mid);66 67 }68 }

【例题2Poj2728Desert King——最优比率生成树】

View Code

1 #include
      
         2 #include
       
          3 #include
        
           4 #include
         
            5 #include
          
             6 #include
           
             7 #include
            
              8 #include
              9 #define Min(a,b) a>b?b:a 10 #define Max(a,b) a>b?a:b 11 #define CL(a,num) memset(a,num,sizeof(a)); 12 #define inf 9999999 13 #define maxn 1030 14 #define eps 1e-6 15 16 using namespace std; 17 struct node 18 { 19 double x,y,h; 20 }p[maxn]; 21 struct cnode 22 { 23 int k; 24 double w; 25 cnode(int kk,double ww): k(kk),w(ww){} 26 friend bool operator < (cnode a,cnode b) 27 { 28 return a.w>b.w; 29 } 30 }; 31 int n; 32 double mat[maxn][maxn],cost[maxn][maxn],dis[maxn],vis[maxn]; 33 priority_queue
              
               que; 34 void init() 35 { 36 int i,j; 37 for(i=0;i<=n;i++) 38 { 39 for(j=0;j<=n;j++) 40 { 41 mat[i][j]=inf; 42 cost[i][j]=0; 43 } 44 } 45 } 46 47 double prim(double mid) 48 { 49 int i,j,k; 50 double res=0; 51 for(i=0;i<=n;i++) 52 { 53 dis[i]=inf; 54 vis[i]=0; 55 } 56 dis[0]=0; 57 58 for(i=0;i
               
                t) 75 { 76 dis[j]=t; 77 } 78 } 79 80 } 81 return res; 82 } 83 int main() 84 { 85 int i,j; 86 while(scanf("%d",&n),n) 87 { 88 for(i=0;i
                
                 max)max=w;103 cost[i][j]=w;104 cost[j][i]=w;105 106 }107 108 double l=0,r=max,mid;109 while(r-l>eps)110 {111 mid=(l+r)/2;112 if(prim(mid) >= 0)113 {114 115 l = mid;116 }117 else r = mid;118 119 }120 printf("%.3lf\n",mid);121 }122 123 }

【例题3Poj3621Sightseeing Cows——最优比率环】

spfa （判负环）

View Code

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #include
          
            6 #include
           
             7 #include
            
              8 #include
              9 #define Min(a,b) a>b?b:a10 #define Max(a,b) a>b?a:b11 #define CL(a,num) memset(a,num,sizeof(a));12 #define inf 999999913 #define maxn 103014 #define eps 1e-615 using namespace std;16 struct node17 {18 int u;19 int w;20 node (int uu,int ww):u(uu),w(ww){}21 };22 vector
              
               p[maxn];23 int n,m;24 queue
               
                que;25 double dis[maxn];26 int vis[maxn],tol[maxn],a[maxn];27 bool spfa(double mid)28 {29 int i;30 while(!que.empty())que.pop();31 32 33 for(i=1;i<=n;i++)que.push(i);34 35 for(i=1;i<=n;i++)36 dis[i]=inf;37 38 CL(vis,true); CL(tol,0);39 40 while(!que.empty())41 {42 int u=que.front();que.pop();43 vis[u]=0;44 for(i=0;i
                
                 t+dis[u])50 {51 tol[v]++;52 dis[v]=t+dis[u];53 if(tol[v]>=n)return true;54 if(!vis[v])55 {56 vis[v]=1;57 que.push(v);58 }59 60 }61 62 }63 }64 return false ;65 }66 int main()67 {68 int i,x,y,z;69 while(scanf("%d%d",&n,&m)!=EOF)70 {71 for(i=1;i<=n;i++)scanf("%d",&a[i]);72 for(i=0;i<=n;i++)p[i].clear();73 74 75 while(m--)76 {77 scanf("%d%d%d",&x,&y,&z);78 p[x].push_back(node(y,z));79 80 }81 double l=0,r=2500,mid,ans=-1;82 while(r-l>eps)83 {84 mid = (l+r)/2;85 if(spfa(mid))86 {87 ans=mid;88 l=mid;89 }90 else r=mid;91 }92 if(ans<-1)puts("0");93 else printf("%.2lf\n",ans);94 95 }96 }

转载于:https://www.cnblogs.com/acSzz/archive/2012/07/29/2614116.html

你可能感兴趣的文章