浅谈01分数规划

01分数规划

什么是01分数规划？

分数规划用来求一个分式的极值。

给出$a_i$和$b_i$，求一组$w_i$ ∈ {0，1}，最小化或最大化

$$\frac{\sum_{i=1}^n a_i \times w_i}{\sum_{i=1}^n b_i \times w_i}$$

另一种描述：每种物品有两个权值$a$和$b$,选出若干个物品使得$\frac{\sum a}{\sum b}$ 最大/最小。

在图论问题（求负环、最小生成树和最短路）中类似于$\frac{\sum a}{\sum b}$这样形式的题，称为01分数规划

有什么用？

做图论题会用到

怎么用？

二分

例如 观光奶牛 这道题
判断图中是否存在环$C$，使得$\frac{\sum a}{\sum b} \gt mid$
$\frac{\sum a}{\sum b} \gt mid \Leftrightarrow \sum a \gt mid \times \sum b \Leftrightarrow \sum a - mid \times \sum b \gt 0$
所以公式可以转换为:$\sum(a_i - mid \times b_i) \gt 0) \Leftrightarrow 图中是否存在正环$

01分数规划思路

1. 二分出一个常值
2. 整理不等式，重新定义点权/边权
3. 做图论算法

参考文献：
OI Wiki分数规划