01分数规划

例：给出 $n$ 个数对，$a_i$，$b_i$，选出 $m$ 个数对，使得 $\sum \frac{a[i]}{b[i]}$ 达到最大值。

思路：

首先如果选取 $i$，定义 $x[i]=1$ 否则 $x[i]=0$。

$R=\sum \frac{a[i]\times x[i]}{b[i]\times x[i]}$。

目标：求 $R$ 的最大值。

定义函数，

$F(L)=\sum (a[i]\times x[i]) -L\times \sum (b[i]\times x[i])= \sum (a[i]-L\times b[i])\times x[i]$

令：$d[i]=a[i]-L\times b[i]$，

$F(L)=\sum(d[i]\times [i])$。

$F(L)$ 与 $R$ 的关系：

$L$ 就是目标式中的 $R$，最大化 $R$ 也就是最大化 $L$。

假设我们已知在存在一个方案 $X$ 使得 $F(L)>0$。

$F(L)=\sum (a[i]\times x[i])-L\times \sum (b[i]\times x[i])>0$。

即 $\sum \frac{a[i]\times x[i]}{b[i]\times x[i]}>L$。

说明了这组方案可以得到一个比现在的 $L$ 更优的一个 $L$。

$d[i]=a[i]-L\times b[i],F(L)=\sum (d[i]\times x[i])$。

显然：$d$ 数组是随着 $L$ 的增大而单调减的。

存在一个临界的 $L$ 使得不存在一种方案，能够使 $F(L)>0$.。

这个时候的 $L$ 就是我们要求的最优解。

如何求解 $L$？

二分法即可。

L:=...;R:=...;
Repeat
  Mid:=(L+R)/2;
  For I=1..X do D[i]:=A[i]-Mid*B[i];//根据Mid计算D数组
  if 检查（Mid）成功 then L:=Mid else R:=Mid；

Until abs(L-R)<Eps;

改进

Dinkelbach算法

因为 $F(L)>0$,我们已经知道了 $R$ 是一个更优的解，与其漫无目的的二分，为什么不将解移动到 $R$ 上去呢？

求 01 分数规划的另一个方法就是，基于这样的一个思想，并不会去二分答案，而是先随便给定一个答案，然后根据更优的解不断移动答案，逼近最优解。

L:=随便什么东西;
Repeat
  Ans:=L;
  For I=1..X do D[i]:=A[i]-L*B[i];//根据L计算D数组
  检查解并记录;
  p:=0;q:=0;
  for I=每一个元素 do
     如果元素I在解中
        begin
          p:=p+A[i];q:=q+A[i];
        end;
  L:=p/q;//更新解
Until abs(Ans-L)<Eps;

模板（POJ2976）

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
int n,k;
double a[1010],b[1010];
double d[1010],eps=1e-6,ans;
int main()
{
	while(scanf("%d%d",&n,&k)!=EOF&&(n|k))
	{
		memset(a,0,sizeof(a));
		memset(b,0,sizeof(b));
		memset(d,0,sizeof(d));
		for(int i=1;i<=n;i++)
			scanf("%lf",&a[i]);
		for(int i=1;i<=n;i++)
			scanf("%lf",&b[i]);
		double l=0.0;
		double r=1.0;
		while((r-l)>eps)
		{
			double mid=(l+r)/2;
			for(int i=1;i<=n;i++)
				d[i]=a[i]-b[i]*mid;
			sort(d+1,d+n+1);
			ans=0;
			for(int i=k+1;i<=n;i++)
				ans+=d[i];
			if(ans>=0)
				l=mid;
			else
				r=mid;
		}
		l*=100.0;
		printf("%.0lf\n",l);
	}
	return 0;
}