所谓01分数规划是这么一个问题：

定义f=sigma(ai*xi)/sigma(bi*xi)，xi可以取{0,1}，可能还有一些限制条件比如x1=1时x2!=1，而目标是让f最大/最小化（保证bi,ai>0）。下面以最大值为例。

直接做并没有什么太好的办法，在此考虑将原式变形，sigma(ai*xi)=f*sigma(bi*xi)，继续变形得到sigma[xi*(ai-f*bi)]=0

令g(f)=sigma[xi*(ai-f*bi)]

考虑到bi>0，因此对于一组确定的决策xi来说，g(f)为一个斜率<0的一次函数，因此如果g(fnow)>0，那么就表明这组决策xi比当前fnow的决策更优。

由此衍生出两种算法：二分与dinkelbach算法

二分：每次二分一个fnow，想办法选取一组xi使得g>0（并且满足限制条件），如果成功那么移动下界，否则移动上界。

dinkelbach：先随便定一组决策，然后想办法选取一组xi使得g>0（并且满足限制条件），那么用新的决策替换老的决策。

dinkelbach的时间复杂度是不稳定的，天知道要几步才能爬到最优决策，而二分是稳定的。

----------------------------------------------------------------------------------------------------------

分数规划的题目框架都是一致的，不同的地方在于选取xi并且要求其满足限制条件的那一步。这一步的处理应该才是命题人比较看重的。

以【最优比率生成树】为例。每条边选取有代价和权值，要求权值和除以代价和最大。

每次二分出来一个fnow，计算各条边的wi=-（ai-f*bi），用prim计算最小生成树，如果最小生成树的sigma(wi)>0那么移动下界，否则移动上界。

----------------------------------------------------------------------------------------------------------

01分数规划问题到了这里变得很像01背包，那么相应得还能有各种背包问题在分数规划上的对应【完全分数规划、部分分数规划等等】，但是均可在01分数规划的基础上贪心解决，不再叙述。

----------------------------------------------------------------------------------------------------------