分数规划

概述

分数规划求一个子集，使选中元素的收益之和除以代价之和达到最大或最小，最常见的是每个元素只能选或不选的 01 分数规划。做法是二分最终比值 mid，把每个元素的权值改写为收益减去 mid 乘代价，再判断能否选出一个子集使总权值之和非负：若能则说明真实最优比值不小于 mid，否则更小，据此缩小二分区间。这样就把带分式的最优化转化成一系列可行性判定，判定内部按题目选出使权值和最大的子集即可。随二分收敛便得到最优比值。例题为洛谷 P3199。

参考资料

• 分数规划 - OI Wiki

简介

分数规划 求一个子集，使「选中元素的收益之和除以代价之和」最大或最小，最常见的是每个元素只能选或不选的 01 分数规划。二分答案 $mid$，将每个元素的权值改为 $\text{收益}-mid\times\text{代价}$，再判断是否存在子集使总权值非负，即把分式最优化转化为可行性判定。

例题

洛谷 P3199 [HNOI2009] 最小圈

给定一张 $n$ 个点 $m$ 条带权有向边的图，求一个环，使环上边权的平均值最小。