原博客:http://www.cnblogs.com/KirisameMarisa/p/4187637.html
换种思路,我们在判断一个当前的r的时候需要去求一个F(r)max,在二分之中我们仅仅判断了F(r)max与0的关系,这是利用率比较低的。其实我们可以将F(r)max利用起来。找到F(r)max所在的那一条直线,然后将r移动到这条直线的截距上面去(如下图,找到当前的F(r)max所在的直线,将r移动到r4上面去,这样做甚至只要2步即可到位)
它实质上是一种迭代,他是基于这样的一个思想:他并不会去二分答案,而是先随便给定一个答案,然后根据更优的解不断移动答案,逼近最优解。由于他对每次判定使用的更加充分,所以它比二分会快上很多。
在这个算法中,我们可以将r初始化为任意值,不过由于所有直线都只有y轴右边的部分,所以一般将r初始化为0。
例题POJ3111
#define zero(a) fabs(a)<eps
double m[50000+10],w[50000+10];
struct node{double num;int ord;} d[50000+10];
bool cmp(node a,node b){return a.num>b.num;}
int main()
{
int N,K;
scanf("%d%d",&N,&K);
for(int i=0;i<N;i++)
scanf("%lf%lf",&m[i],&w[i]);
double l=0.0,ans;
while(1)
{
ans=l;
for(int i=0;i<N;i++)
{
d[i].num=m[i]-ans*w[i];
d[i].ord=i;
}
sort(d,d+N,cmp);
double p=0.0,q=0.0;
for(int i=0;i<K;i++)
{
p+=m[d[i].ord];
q+=w[d[i].ord];
}
l=p/q;
if(zero(ans-l))
break;
}
printf("%.2f\n",ans);
return 0;
}
不过需要注意的是,并不是可以放弃二分全用Dinkelbach算法。这只是最基本的0-1规划问题, Dinkelbach算法的弊端就是需要保存解。在更加复杂的问题中,有的时候二分更快,有时Dinkelbach算法更快。
二分和Dinkelbach算法写法都非常简单,各有长处,大家要根据题目谨慎使用。