分数规划

分数规划的精度问题

按照理论算法来推，可以知道 $\sum _{i=1}^m{a}_i-b_i\times x\ge 0$，但是在实现中存在精度问题。

一般题目会给定一个精度 $eps$，假设最终的准确答案是 ${\displaystyle \frac{\sum _{i=1}^m{a}_i}{\sum _{i=1}^m{b}_i}\to Ans}$，我们程序求出的答案 $x$，$x$ 的取值范围应该在 $[Ans-eps,Ans+eps]$，转化一下，即 $|{\displaystyle \frac{\sum _{i=1}^m{a}_i}{\sum _{i=1}^m{b}_i}-x|\le eps}$。

那么根据分数规划，可以得到 $\sum _{i=1}^m{a}_i-b_i\times x\le eps$ 或 $\sum _{i=1}^m{a}_i-b_i\times x\ge -eps$。