一、简介

0/1 分数规划是一种求最优比率的算法，一般通过二分实现。

二、解决问题

分数规划是用来求解一个分数表达式的最大值/最小值。例如有 $n$ 个物品，每个物品都有两个权值 $a_i$ 和 $b_i$，你可以取其中任意件物品，求 $\frac{\sum_{i=1}^k a_i}{\sum_{j=1}^k b_j}$ 最大值。

三、解决方法

我们一般通过二分来求解。

我们二分最终答案 $ans$，设 $val=\sum_{i=1}^k a_i,wei=\sum_{j=1}^k b_j$，那么显然有

$\frac{val}{wei}\leq ans$

移项得

$val\leq ans\times wei$

$val-ans\times wei\leq 0$

$\sum_{i=1}^k a_i-ans\times \sum_{j=1}^k b_j\leq 0$

$\sum_{i=1}^k a_i-ans\times b_i\leq 0$

一般我们贪心地选择 $k$ 个然后判断是否小于等于 $0$。

四、例题

1. 0/1 分数规划 $+$ 背包

P4377 [USACO18OPEN]Talent Show G

首先求 $\frac{\sum_{i=1}^k t_i}{\sum_{j=1}^k w_j}$ 的最大值，还是普通的 0/1 分数规划，不过本题多了个限制：$\sum_{j=1}^k w_j$ 不小于 $W$，那么我们在 check 的时候不能简单地通过贪心来求解了，而是需要通过背包来判断，注意 $\geq W$ 的都当 $W$ 来算。

2. 0/1 分数规划 $+$ 环

P3199 [HNOI2009]最小圈

大致是每条边都有两个权值 $a_i$ 和 $b_i$，找到一个环使得 $\frac{\sum_{i=1}^k a_i}{\sum_{j=1}^k b_j}$ 最小。那么直接二分 $ans$，然后在图上找一个负环，最好用 dfs，似乎比 spfa 快。

P2868 [USACO07DEC]Sightseeing Cows G

这题求最大值，那么也就是要找个正环，可以将其转化为求负环，将边权取负后求负环即可。