什么是0/1分数规划？
大概就是这样一类问题：
有一堆物品，选择一个物品都有一个收益ai,有一个代价bi,
选择若干个（也可能有限制）物品，
使得
最小（大）
看上去很难的样子？
其实化一下式子就变简单啦！
我们设
，显然当满足式子的x最小的时候，就最小了
我们移一下项：
--->$sum_{i = 1}^{n} a[i] - x * b[i] le 0$
相当于就只用判断这个式子的真假了～～～
显然这个式子是符合二分条件的，因此我们可以二分x的值
分数规划的题不管是取最大还是最小都是二分+check（）
但是每道题对于合法的选择集合有不同的限制，比如必须是环，必须是树，必须……
诸如此类的很多，这个时候就需要根据具体的题目来调整check函数了，
比如如果要求是环，可以将check变成找负环，要是没要求还可以直接贪心，
分数规划只是提供了一个二分的方法，
以下为几道例题（我做过的）：