博客

原博客：

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算法写法都非常简单，各有长处，大家要根据题目谨慎使用。