个人对01分数规划的理解是:

01分数规划是利用二分的思想,不断地对答案进行二分验证,使得答案趋近于正确值,最后在精度允许的情况下得到最终的正确答案。

先来举个例子,假设有一堆物品,价值为分别为v_i(v_i\geq0),代价分别为w_i(w_i\geq0)。每种物品只有选和不选,请选出一些物品,使他们的收益和最大(为了体现出01规划中01的思想,我们规定这里的w>=v,保证0\leq ans \leq 1, 当然01规划肯定不是说只解决答案在01之中的问题,具体我们在下面讲解)。

我们假设最终的正确答案是ans,那么最后我们得到的答案肯定是\sum v_i / \sum w_i=ans
把这个式子稍微整理一下,变成:\sum v_i - ans \times \sum w_i=0
网上很多这里就开始定义为不等式了,我认为不着急,我们先来思考一下。

(不如先在脑海中思考一下零点的求法?)

由于我们现在不知道具体的答案,但是我们知道答案的上限和下限:L=0, R=1。现在开始对答案进行二分验证,可以定义mid=\frac{(l+r)}{2}。我们把未知的ans用已知的mid替换掉,由于我们上面变换后的式子说明了当ans为正确答案时,左边应该是等于0的。
所以,如果代入的mid使得整个左边式子大于0,那么我们就考虑把左边变小,如果代入的mid使得整个左边式子小于0,那么我们就考虑使mid变大。
定义不等式为:\sum v_i - ans \times \sum w_i\ge0,这样就可以直接判断左边大小了(具体请看下面代码)。
所以,现在我们知道那个不等式是用来干啥的了吧。对,就是用来判左边式子大小的,这就是二分的思想。

所以二分的基本代码模板大概就是这样的:

#include <iostream>
using namespace std;
const double L=0, R=1;
const double eps=1e-4;
bool check(double mid){
    double sum=0;
    //这里编写计算过程,也许需要贪心?
    return sum>=0;
}
int main()
{
    double l=L, r=R;
    while(r-l>=eps){
        double mid=(l+r)/2;
        if(check(mid))l=mid;
        else r=mid;
        cout<<l<<endl;
    }
    return 0;
}


最后来讲一下区间的问题,前面说了,01分数规划并不是说就是0到1之间枚举,也可以是整数之间,或者更大的浮点数之间进行枚举验证。如果是以题目给出的范围来确定区间,那么二分的区间一定要设置好,刚好等于区间都可能不行,最好是稍大一点。而另外一种方法就是在输入数据的过程中进行区间值的的更新,这样就能减少最后枚举的数,但是由于是二分的,所以大部分情况下也减少不了多少次数。还有就是浮点数的精度要控制好,当然,最好的办法就是用一个k值来统计枚举的次数,freeloop说200次已经差不多是极限了,自己看着去考虑就好。



相关链接:


POJ 2976 - Dropping tests(基础01分数规划)

POJ - 2728 Desert King (最优比率生成树)

POJ - 3621 Sightseeing Cows (最优比率生成环)