最大化平均值（01分数规划）¶

01分数规划又名最大化平均值。第一次在《挑战程序设计竞赛》里遇到。

基本模型：

一类物品，收益为 $a_i$ ，代价为 $b_i$ ，从中选出 $k$ 个，使 $\frac{\sum_{i = 1}^ k a_i}{\sum_{i = 1}^ k b_i}$ 最大。

一个很典型的**错误**想法是，计算每个物品的 $a_i / b_i$ ，然后排序，取最大的 $k$ 个。

比如一类物品，收益依次为2，5，2，代价依次为2，3，1，取k为2。如果按照**错误**的思路，那么应该选前两个物品，结果为0.741，但是实际上取第一个和第三个结果最大为0.75。

这时应该采取二分的方法来解决。方法在《挑战程序设计竞赛》里已经分析的很清楚了，这里举一个典型的应用。

典型题目：

POJ 2976 Dropping tests

注意结果是四舍五入，所以需要(int)(res + 0.5)。

Dinkelbach算法¶

对于 01 规划问题，除了利用基本的二分答案来解决外，还有一个常用的算法：Dinkelbach 算法

Dinkelbach 算法是一种的迭代算法，其核心思想是：对于一个值 λ ，我们找到其最优解 x，然后再用解 x 来代替 λ ，即令 λ=f(x)，然后继续迭代，直到 λ 的值不再变动，此时即得出最优解。

典型应用¶

最有比率生成树¶

问题：**对于给定的带权无向图 G，对于图中的每条边 edge[i]，都有 value[i] 与 cost[i]，现在要求一棵生成树 T，使得 $\frac{\sum value[i]}{\sum cost[i]}$ 最大化或最小化，这个生成树 T，即为**最优比率生成树

**解决：**如果一条边 edge[i]∈T，那么 x[i]=1，否则 x[i]=0，因此可以直接套用 01 规划分数模型

**二分法：**二分答案 mid，对边重赋值 weight[i]=value[i]-mid*cost[i]，由于是生成树，因此边的数量固定为 n-1 条，因此如果要最大化，只要选取前 n-1 大的 weight[i]，也即求最大生成树，如果要最小化，就求最小生成树，最后按最大生成树的权值正负性进行二分

**Dinkelbach 算法：**设置初始值 init，对边同样重赋值 weight[i]=value[i]-init*cost[i]，对于最大化来说，求最大生成树，找到其边集，对其边集找横截距当作下一次的答案，进行迭代

最优比率环¶

最大稠密子图¶

典型题目¶

Dropping tests（POJ-2976）(标准模型+二分解法)
Dropping tests（POJ-2976）(标准模型+Dinkelbach 算法)
Desert King（POJ-2728）(最优比率生成树+二分解法)
Desert King（POJ-2728）(最优比率生成树+Dinkelbach 算法)
Sightseeing Cows（POJ-3621）(最优比率环+二分解法)
Hard Life（POJ-3155）(最大密度子图+最大权闭合图)
Hard Life（POJ-3155）(最大密度子图+最小割)
洛谷 4377 Talent Show