最近入门了 01 分数规划，于是写篇博客纪念

(如果cnblogs上的格式您实在受不了，请转至我的洛谷blog，并且那里的讲解会稍微详细一些，另外，更新内容也在我的洛谷博客中)

分数规划是一项不常用到的（但还蛮实用的）算法，一般来讲就是求一个最优比率。

分数规划顾名思义就是求一个分数表达式的最大（小）值。

比如说有 n 个物品，每个物品有两个权值 a 和 b ，然后让你选出任意件数（但可能会有限制）的物品，使得两个权值和间的比值最大，即求 \(\dfrac{\sum_{i=1}^{k} a[i]}{\sum_{j=1}^{k} b[j]}\) （在这里 \(1-k\) 为挑出的 k 件物品）的最大值，然后对选择物品方面给出一定的限制条件，那么一道 0/1 分数规划的题目就完成了

分数规划有两种求解方法，一种是 二分法，而另一种则是 Dinkelbach 算法，一般来讲我们选用第一种方法进行分数规划求解

问题同上，求 \(\dfrac{\sum_{i=1}^{k} a[i]}{\sum_{j=1}^{k} b[j]}\) 的最大值，然后加上一个限制：\(k>=W\)

我们令 \(sum=\sum_{i=1}^{k} a[i] ,\ tot=\sum_{j=1}^{k} b[j]\) ，\(k>=W\)

然后假设问题中的最优解为 \(ans\) ，那么必然有：