要说梦想人生，你便活在其中

歌曲

綺羅キラ-ずっと真夜中でいいのに

---

本质

一种数学优化方法

---

用途

主要用于求解目标函数和约束条件中包含分式形式的问题

---

实现

一般使用二分法,步骤如下:

(1)预估规划值的上下界，一般规划值是一个百分数∈[0,1]，不一般的当我没说，但可以分离为一个常数乘上一个百分数的形式

(2)对式子$\sum_{i=1}^{n} a_i \times x_i \over \sum_{i=1}^{n} b_i \times x_i$进行变形可得不等式$\sum_{i=1}^{n} a_i-l \times l*b_i \geq 0$，其中$l$就是我们想要的规划值，观察不等式易得$\sum_{i=1}^{n} a_i-l \times l*b_i$与$l$成正比关系，所以可用二分枚举$l$的值

(3)确定精确值$\epsilon$(一般写作$eps$)，当$r-l$的值小于$\epsilon$时称我们找到了满足条件的一个解

BUT

我们还有一个更快的方法$Dinkelbach$算法，这个算法其实就是以二分函数图像的单调性为原理，利用了check中计算得出的结果，通过改变二分枚举的中间点在图像上的位置来优化二分

另外这个算法复杂度就是$O(玄学)$的，出题人一般不会卡(想卡也难卡，因为初始点可以是任意的，这就相当于随机算法了啊！鬼知道你乱搞出来的初始点会不会就是答案了)，但是讲道理,这个算法效率确实没有保障......,所以我们一般还是选择使用普通二分解决此类问题

Dinkelbach参考代码#1339.Dropping tests

#include<stdio.h>
#include<algorithm>
#include<math.h>
using namespace std;
typedef struct Res
{
	double a, b;
	double d;
	bool operator < (const Res &b) const
	{
		if(d>b.d)
			return 1;
		return 0;
	}
}Res;
Res s[1005];
int main(void)
{
	int i, n, k;
	double cnt, sa, sb;
	while(scanf("%d%d", &n, &k), n!=0 || k!=0)
	{
		k = n-k;
		for(i=1;i<=n;i++)
			scanf("%lf", &s[i].a);
		for(i=1;i<=n;i++)
			scanf("%lf", &s[i].b);
		cnt = 0;
		while(1)
		{
			for(i=1;i<=n;i++)
				s[i].d = s[i].a-cnt*s[i].b;
			sort(s+1, s+n+1);
			sa = sb = 0;
			for(i=1;i<=k;i++)
			{
				sa += s[i].a;
				sb += s[i].b;
			}
			if(fabs(sa/sb-cnt)<0.00001)
				break;
			cnt = sa/sb;
		}
		printf("%.0f\n", cnt*100);
	}
	return 0;
}

---

代码

bool judge( double x )
{
	for( int i=1;i<=n;i++ )
	{
		c[i]=a[i]-x*b[i];//计算每组a,b对应的分数值
	}
	sort( c+1,c+n+1 );
	double sum=0;
	for( int i=n;i>=n-k+1;i-- )//为使sum尽可能满足条件,取最大的k组c值
	{
		sum+=c[i];
	}
	return ( sum >= 0 );
}

double l=0, r=1;
while( fabs( r-l ) > esp )//如果精确不足继续循环
{
	double m=( r+l )/2;//二分枚举
	if( judge( m ) )//sum比0大,l值还能增加
	{
		l=m;
	}
	else//sum比0小,l值只能减小
	{
		r=m;
	}
}

---

注意

对于精确值，为防止精确度不够(例如需要四舍五入时)，一般会在题目要求答案的精确值上在乘个$10^{-1}$，以确保答案不会因为精度问题而出错