分数规划小记

OI-算法

---

分数规划用于求解一类分式极值。

0-1分数规划

0-1分数规划是分数规划的一种特殊情况，也是最经典的分数规划

他用于求解 $\frac{\sum_{i=1}^{n}{a_iw_i}}{\sum_{i=1}^{n}{b_iw_i}}$ 其中 $w_i \in [0,1]$ ，这样形式式子的极值。

形象地描述就是在 $n$ 个物品中决定每个物品选或不选，求一个比例的极值。

下面以求解最大值为例。

我们考虑二分这个极值，则问题转化为 check ：

$$\frac{\sum_{i=1}^{n}{a_iw_i}}{\sum_{i=1}^{n}{b_iw_i}} > mid$$

稍微推下柿子：

$$\sum_{i = 1}^{n}{w_i\times(a_i - mid \times b_i)} > 0$$

则以 $a_i - mid \times b_i$ 为新的权值，考虑能否按限制选出大于 $0$ 的解即可。

例题

POJ2976 模板题

Luogu4377

需要分母至少选出 $W$ 的权值，考虑一个 01背包，以 $b_i$ 做重量，以 $a_i - mid \times b_i$ 做价值

POJ2728

最小比例生成树，将 $a_i - mid \times b_i$ 做边权，跑遍生成树就行了（卡Kruskal，需要Prim）

HNOI2009最小圈

将 $1$ 看做 $b_i$，那么将 $a_i - mid$ 做为边权，要求的就是有无环权值和 $<0$

问题转化为判负环问题，SPFA跑一遍即可。

JSOI2016最佳团体

先套个分数规划，那就是要在树上以根为中心选一个 $k$ 个点的连通块，跑个树上背包就好了。

SDOI2017新生舞会

套个分数规划，问题转化为一个二分图最大权匹配问题，跑个费用流即可。

UVA1389

最大密度子图模板题。

总结

分数规划是类很套路的处理技巧，他可以将难以求解的比例式转化，转化为其他好处理的问题，而其题目难度实则往往在于转换后的问题。