转载请注明出处：http://www.cnblogs.com/KirisameMarisa/p/4187637.html
题目链接：http://acm.nyist.net/JudgeOnline/problem.php?pid=914
问题描述：有N个物体，它们的利益用v[i]表示，代价用c[i]表示。现在要在这N个物体中选取K个物体，使得选出来的这K个物体的总利益除以总代价达到最大值。即
取得最大值。
问题转化：构造一个x[N]的数组，表示每个数取或不取的状态，显然每一个x[i]只有两个取值：0和1，其中1表示取，0表示不取。则整个式子也就可以变成目标式：
值得注意的是：上式中的r是每一组x对应求得的当前答案，而我们的目的就是要找到一组x使得求出来的r得到最大值R！（这很重要！）
一、二分法
进一步对式子进行处理：
简单的一项处理：
构造一个函数：
其中F(r)在平面坐标系上体现为一条直线，每一组x[i]都分别唯一地对应一条直线，这些直线的截距均大于等于0、斜率均小于等于0。而这些直线在X轴上的截距就是这一组x求出来的r，而截距的最大值就是我们要求的R。（如下图所示）
在X轴上面任取一个r，如果至少有一条直线的F(r)>0，那么说明了什么呢？
说明至少还有一条直线与X轴的交点在它的右边，那么这个r一定不是最大值，真正的最大值在它的右边。反之，如果所有的F(r)都小于0，那么真正的最大值在它的左边
那么前面的结论就可以换种说法，因为我只需判断最大的那个F(r)的正负性就行了：
随便取一个r，如果F(r)max>0，则结果R>r，反之若F(r)max<0，则结果R<r。直到找到使F(r)max=0的r，那个r就是我们要找的结果R
显然这是一个令人感到兴奋的结论，因为我们自然而然就想到了一种方法：二分法！
至此，还有一个小小的问题没有解决，那就是F(r)max怎么求？
至此，问题全部解决！
#define eps 1e-8
#define zero(a) fabs(a)<eps double v[MAXN],c[MAXN],d[MAXN]; int main()
{
int N,K;
scanf("%d%d",&N,&K);
for(int i=;i<N;i++)
scanf("%lf%lf",&v[i],&c[i]);
double l=0.0,r=10000000.0;
while(!(zero(r-l))) //二分终止条件，利用double的精度控制
{
double mid=(r+l)/2.0;
for(int i=;i<N;i++)
d[i]=v[i]-mid*c[i];
sort(d,d+N);
double sum=0.0;
for(int i=N-;i>=N-K;i--)
sum+=d[i];
if(sum>=) l=mid;
else r=mid;
}
double ans=l;
printf("%.2lf\n",ans);
return ;
}
二分法可以轻松水过南阳理工学院oj上的原题和ghbgh出的上大oj上的改题甚至是POJ的2976这些最基本的0-1分数规划问题。不过，用这种方法去做POJ上面的3111时却直接TLE了orz。。。。
二分是一个非常通用的办法，但是我们来考虑这样的一个问题，二分的时候我们只是用到了F(r)>0这个条件，而对于使得F(r)>0的这组解所求到的R值没有使用。因为F(r)>0,我们已经知道了R是一个更优的解，与其漫无目的的二分，为什么不将解移动到R上去呢？
我们再次回到函数表达图：
这个是二分的原理表现，在图中，我们取左界为0，右界为足够大，画出中间的(左+右)/2，发现此时F(r)max是大于0的，那么继续将左界移向(左+右)/2，继续二分，直到找到R为止。
但是我们换种思路，我们在判断一个当前的r的时候需要去求一个F(r)max，在二分之中我们仅仅判断了F(r)max与0的关系，这是利用率比较低的。其实我们可以将F(r)max利用起来。找到F(r)max所在的那一条直线，然后将r移动到这条直线的截距上面去（如下图，找到当前的F(r)max所在的直线，将r移动到r4上面去，这样做甚至只要2步即可到位）
这就是下面要介绍的方法：
二、Dinkelbach算法
它实质上是一种迭代，他是基于这样的一个思想：他并不会去二分答案，而是先随便给定一个答案，然后根据更优的解不断移动答案，逼近最优解。由于他对每次判定使用的更加充分，所以它比二分会快上很多。
在这个算法中，我们可以将r初始化为任意值，不过由于所有直线都只有y轴右边的部分，所以一般将r初始化为0。
double m[+],w[+];
struct node{double num;int ord;} d[+];
bool cmp(node a,node b){return a.num>b.num;}
int main()
{
int N,K;
scanf("%d%d",&N,&K);
for(int i=;i<N;i++)
scanf("%lf%lf",&m[i],&w[i]);
double l=0.0,ans;
while()
{
ans=l;
for(int i=;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=;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 ;
}
不过需要注意的是，并不是可以放弃二分全用Dinkelbach算法。这只是最基本的0-1规划问题， Dinkelbach算法的弊端就是需要保存解。在更加复杂的问题中，有的时候二分更快，有时Dinkelbach算法更快。
二分和Dinkelbach算法写法都非常简单，各有长处，大家要根据题目谨慎使用。
by---Kirisame_Marisa 2014-12-26 22:31:43
