2023年7月30日发(作者：)
浅谈01分数规划⽂章⽬录概念01分数规划⼀般是处理这样⼀类问题：给定 n 个⼆元组 ( Ai , Bi )，让你从中选择 m 个组 (m<=n）使得∑Akk=1Bkm最⼤或最⼩，通常分为三类Ⅰ：基础01分数规划模板题(POJ2976)给定 n 个⼆元组 ( Ai , Bi )，从中选择 m=n-k 个求∑Akk=1Bkm的最⼤值我们假设这个最⼤值为 L，即∑k=1Ak∑Ak∑∑mL=k=1Bk=∑k=1Bk<=>k=1Ak−k=1Bk∗L=0mmmm⽐较明显的⼀种做法是⼆分枚举 L，然后按照 Ai-Bi*L 从⼩到⼤排序，取后 n-k 个的和 sum，若 sum >=0 则表明 L 还可以继续增⼤，更新下界，否则更新上界。#include
double l=0,r=1.1; while(r-l>=eps) { double m=(l+r)/2; if(check(m)) l=m; else r=m; } double ans=(l+r)/2; printf("%.0fn",ans*100); }}这⾥重点讲述另⼀种做法，Dinkelbach 算法 ，我们随便设定⼀个初始值 L ，然后进⾏如下流程：for(int i=1;i<=n;i++) res[i]=A[i]-B[i]*L;sort(res+1,res+n+1);double tmp=0;for(int i=k+1;i<=n;i++) tmp+=res[i];我们已知∑mk=1Ak−k=1Bk∗∑mL=tmp现在我们⽤这选定的 m 个⼆元组去构造出∑mk=1Ak−k=1Bk∗∑mnewL=0分三类情形讨论：① tmp>0：明显有newL>L前者是更优解，更新 L = newL② tmp<0 : 这种情况下 L 肯定已经⼤于最优解了，此时肯定有newL
#include double L=1,ans; while(1) { ans=L; for(int i=1;i<=n;i++) res[i]=(node){A[i]-B[i]*L,i}; sort(res+1,res+n+1); double a=0,b=0; for(int i=k+1;i<=n;i++) a+=A[res[i].id],b+=B[res[i].id]; L=a/b; if(abs(ans-L)<=eps) break; } printf("%.0fn",ans*100); }} 此外，初始值的选定也会稍稍影响测评效率(拿这题来说，初始值设为 0 测试时间是47ms，⽽初始值设为 1 的 测试时间则都是32ms ，应该是测试数据答案⼤部分偏向⼤⼀些)，所以⼀般可根据题意初始化，若题意求最⼤，则初始化为上限值，若题意求最⼩，则初始化为下限值。Ⅱ：最优⽐率⽣成树模板题(POJ2728)给定平⾯坐标系上的 n 个点，每个点都有权值，两点的花费是两点权差的绝对值，两点的收益是两点的距离，求⼀个⽣成树，使得树上的 花费/收益 最⼩我们还是假设最⼩值为 L ，设选定的 m = n-1 条边的收益和花费⼆元组分别为 (val[i],cost[i])，则∑cost[i]∑∑L=i=1val[i]<=>i=1cost[i]−i=1val[i]∗L=0mmm和 基础01分数规划 ⼀样我们还是可以选择⼆分枚举 L ，按照 cost[i]-val[i]*L 作为两点的边权求最⼩⽣成树，设当前最⼩⽣成树的总权值为tmp=∑i=1mcost[i]−∑i=1mval[i]∗L这⾥是求最⼩，若 tmp<=0，则更新上界，否则更新下界(由于是稠密图，所以最⼩⽣成树⽤prim求)#include double cal(int i,int j){ double a=x[i]-x[j],b=y[i]-y[j]; return sqrt(a*a+b*b);}double prim(double m){ bool vis[N]={0,1}; double c[N],sum=0; int tot=1,u=1,v; while(tot if(res>c[i]){ res=c[i]; v=i; } } } sum+=c[v]; vis[v]=1; u=v; tot++; } return sum;}int main(){ while(~scanf("%d",&n)&&n) { for(int i=1;i<=n;i++) scanf("%d%d%d",&x[i],&y[i],&z[i]); for(int i=1;i<=n;i++) for(int j=i+1;j<=n;j++) { val[j][i]= val[i][j]=cal(i,j); cost[j][i]=cost[i][j]=abs(z[i]-z[j]); } double l=0,r=100; while(abs(r-l)>eps) { double m=(l+r)/2; if(prim(m)>=0) l=m; else r=m; } printf("%.3fn",l); }}这题还是可以⽤ Dinkelbach 考虑，它依旧满⾜∑i=1mcost[i]−∑i=1mval[i]∗L=tmp这样的形式，所以我们还是 ⽤旧 L 选择的 n-1 条边去构造 newL 使得∑i=1mcost[i]−∑i=1mval[i]∗newL=0⽽不断去逼近最终答案#include double cal(int i,int j){ double a=x[i]-x[j],b=y[i]-y[j]; return sqrt(a*a+b*b);}}double prim(double m){ bool vis[N]={0,1}; double c[N],COST=0,DIS=0; int tot=1,u=1,v,pre[N]; while(tot if(res>c[i]){ res=c[i]; v=i; } } } COST+=cost[pre[v]][v]; DIS+= val[pre[v]][v]; vis[v]=1; u=v; tot++; } return COST/DIS;}int main(){ while(~scanf("%d",&n)&&n) { for(int i=1;i<=n;i++) scanf("%d%d%d",&x[i],&y[i],&z[i]); for(int i=1;i<=n;i++) for(int j=i+1;j<=n;j++) { val[j][i]= val[i][j]=cal(i,j); cost[j][i]=cost[i][j]=abs(z[i]-z[j]); } double l=0,ans; while(1) { ans=l; l=prim(l); if(abs(ans-l)<=eps) break; } printf("%.3fn",ans); }}Ⅲ：最优⽐率环模板题(POJ3621)给定⼀个有向图，每个点有点权，每条边有边权，求图上的⼀个环，这个环的 点权和/边权和 最⼤，找到这个最⼤值我们假设这个最⼤值为 L ，则对于所有图上的环来说，每个环肯定满⾜点权和边权和<=L，即(点权和)−(边权和∗L)<=0反过来⼀下(边权和∗L)−(点权和)>=0可以明显的看出，只有这个 L >= 最优解 的时候，图上所有的环关于上式才⼀定成⽴，否则的话 L 就⽐最优解⼩，⽽判断上式是否存在<0的情况等价于以 (点权*L-边权) 为 边判断负环是否存在，所以可以⽤⼆分+SPFA 解决这个问题#include scanf("%d",&val[i]); for(int i=1,u,v,w;i<=m;i++) scanf("%d%d%d",&u,&v,&w),add(u,v,w); double l=0,r=10000; while(abs(r-l)>eps) { double mid=(l+r)/2; if(SPFA(mid)) l=mid; else r=mid; } printf("%.2f",l);}这题可不可以⽤ Dinkelbach 考虑呢，理论上肯定是可以的，但是难点就在于每次必须要记录这个具体的环来构造，显然找具体环的代价太⼤，得不偿失，所以这题还是⼆分更好。总结由上可以总结，对于01分数规划问题(maybe⼤部分)，理论上都可以⽤ ⼆分 或者 Dinkelbach 来解决，⽽ 后者对答案的逼近效率⼀般是⾼于前者的，但是 Dinkelbach 每⼀次逼近的时候需要记录具体的⼆元组来构造，会造成额外的时空开销(视题意⽽定)，所以 需要考虑这个记录的代价 来 选择哪种解法更适合当前问题。
发布者：admin，转转请注明出处：http://www.yc00.com/xiaochengxu/1690723794a408245.html
评论列表（0条）