二分逼近

一、二分迭代逼近算法：给定数n(1≤n≤1000),数k(0≤k≤n),给定n个数对(ai,bi),(i=1,2,3…n);记A(m)=100*∑aimi=1∑bimi=1，在这n个数对中删k对数。使得A(n-k)取最大值。如：n=3,k=1;3个数对为(5,5),(0,1),(2,6)。A(3)=100*5+0+25+1+6=50，Max(A(2))=Max{100*5+05+1,100*5+25+6,100*0+21+6}=100*5+05+1≈83.33解析：假设Max(A(n-k=m))=100*r;则∑aimi=1∑bimi=1=r.=∑aimi=1=r*∑bimi=1=∑(ai−r∗bi)mi=1=0.但是现在面临的问题是怎样获得这个r,而0≤∑aimi=1∑bimi=1≤1的，于是0≤r≤1.现在想采用二分的方法去获取r。设min=0,max=1;mid=(min+max)/2去逼近r,迭代计算每次比较∑(ai−mid∗bi)与0的关系.mi=1这里每次从大到小选取m个ai-mid*bi（1）、∑(ai−mid∗bi)mi=1=0即midr,此时更改min=mid。（2）、∑(ai−mid∗bi)mi=10即midr,此时更改max=mid。当在某次计算是min≡max时所得mid即为r。最后需要解决的一个问题：这个时候到底这剩下的m个数对是哪些呢？让计算机去选取这m个数对。下面在Vc++6.0上实现如上思想。（因篇幅有限只选取部分代码）。inta[1005],b[1005],n,k;doubleminn,maxx,mid,t[1005],sum;doubleeps=1e-5;\\精度设置取10−5intmain(){scanf(%d%d,&n,&k)for(inti=0;in;i++)scanf(%d%d,&a[i],&b[i]);min=0,max=1;\\初始设置while(maxmin+eps)\\当min≡max是跳出{mid=(min+max)/2;\\每次改变midfor(inti=0;in;i++)t[i]=-mid*b[i]+a[i];sort(t,t+n);\\对n个数对按升序排序sum=0;for(inti=k;in;i++)sum+=t[i];\\从大到小选取n-k个值求和if(sum=0)min=mid;elsemax=mid;\\max、min的改变}printf(%d\n,(int)(min*100+0.5));return0;}