01分数规划

二分答案 01分数规划

---

问题模型1--基本01分数规划问题

给定$n$个二元组$(value_i,cost_i)$，其中$value_i$表示的是选择此二元组获得的价值，$cost_i$是选择此二元组付出的代价，假设$x_i\in\{0,1\}$表示第i个二元组选不选，求下式的最大（小）值：

$$R=\frac{\sum_{i=1}^nvalue_i\times x_i}{\sum_{i=1}^ncost_i\times x_i}$$

二分法

$$R_{max}=\frac{\sum_{i=1}^nvalue_i\times x_i}{\sum_{i=1}^ncost_i\times x_i}$$
化简得
$$\sum_{i=1}^ncost_i\times x_i\times R_{max}=\sum_{i=1}^nvalue_i\times x_i$$
设一个函数$f(R)=\sum_{i=1}^nvalue_i\times x_i-\sum_{i=1}^ncost_i\times x_i\times R_{max}$，注意其自变量为$R$
考虑在平面直角坐标系上作图，假设$x_i$不变，那么这个函数就是坐标系中的一条解析式形如$y=b-ax$的直线，每一组$x_i$对应一条直线，而这些直线的斜率又不可能为正（因为$cost_i\times x_i\ge 0$）
所以可以作图如下

对于每一条直线，横截距就是这一组的$R$，那么$R_{max}$就是每条直线横截距的最大值（每组$x_i$对应$R$的最大值）

接下来考虑二分：在图上任取一条垂直于$x$轴的竖线
如果存在某条直线与这条竖线的交点的纵坐标为正，那么最优值一定在当前竖线的右侧
如果所有直线与这条竖线的交点纵坐标为负，那么最优值一定在当前竖线的左侧
如果所有直线与这条竖线的交点纵坐标为负存在直线与这条竖线交点纵坐标为零，那么当前竖线横坐标即为最优值$R_{max}$
选择一个值时需要判断$\max_{i=1}^nf(R)$是否大于0，若大于0那么$R\lt R{max}$
否则$R\ge R_{max}$

Dinkelbach算法

思考上述的二分算法的思路，设二分过程中的一个二分值为x，二分时的判断条件是$\max\{f(x)\}$的正负性，而这个x除了让$L$右移或者$R$左移就没有其他作用了
现在思考某一过程中x与$\max\{f(x)\}$能否再被利用
二分时，假如$\max\{f(x)\}\gt 0$这说明最优解在当前x的右侧，于是让L=x，但是，如果将L移动到$\max\{f(x)\}$对应直线的横截距呢？显然，算法会变得更快。这个思想就是Dinkelbach算法的内涵。
Dinkelbach实质上是一种迭代算法，基于这样的思想：不去二分答案，而是先随便给定一个答案，然后根据更优的解（$\max\{f(x)\}$对应直线的横截距）不断移动答案，逼近最优解。理论上它比二分快些。
在这个算法中，一般将x初始化为0。
不过弊端是需要保存解。

实际应用中这两个算法速度不相上下
不过还是二分更好理解一些

例题：Poj 2976
给出n个物品，每个物品有两个属性a和b，选择n-k个元素，询问$\sum\frac{a_i}{b_i}$的最大值。
$1\le n\le 1000,0\le k\lt n,0\le a_i\le b_i\le 1e9$

裸题，不多说
用的二分

#include <cstdio>
#include <algorithm>
const int N=1001;
const double eps=1e-6;
int n,k,a[N],b[N];
double ps[N];
inline bool judge(double x)
{
    for(int i=1;i<=n;++i)
        ps[i]=a[i]-x*b[i];
    std::sort(ps+1,ps+1+n);
    double ans=0;
    for(int i=n;i>=k+1;--i)
        ans+=ps[i];
    return ans>=0;
}
int main()
{
    while(scanf("%d%d",&n,&k),n|k)
    {
        for(int i=1;i<=n;++i)
            scanf("%d",&a[i]);
        for(int i=1;i<=n;++i)
            scanf("%d",&b[i]);
        double l=0,r=1,mid;
        while(r-l>eps)
        {
            mid=(l+r)/2;
            if(judge(mid))
                l=mid;
            else    r=mid;
        }
        printf("%.0lf\n",l*100);
    }
    return 0;
}

另外还有一种做法：既然可以二分一个值，而且得出一个更优的解，那么就可以在这个解的基础上继续做，直到满足精度
比上面的做法快一些

问题模型2--最优比率生成树

带权无向图G，对于图中每条边$e_i$，都有$value_i$和$cost_i$，现在求一棵生成树T，最大（小）化

$$R=\frac{\sum_{i=1}^nvalue_i}{\sum_{i=1}^ncost_i},e_i\in T$$

解决方法：
套用01分数规划模型，如果$e_i\in T$则$x_i=1$，否则$x_i=0$

二分答案

二分答案ans，边赋值$weight_i=value_i−ans\times cost_i$，因为是生成树，边的数量确定，那么$\max\{f(x)\}$需要选取前$|G|−1$大的$weight_i$，也就是求最大生成树，按最大生成树权值的正负性就可以二分了。最小化就求最小生成树

Dinkelbach算法

当前答案ans，边赋值$weight_i=value_i−ans\times cost_i$，同样求最大生成树，找到$\max\{f(ans)\}$对应的边集${x_i}$，也就是最大生成树的边集。对这个边集找横截距当做下一次答案。
横截距是

$$f(ans)=B-A\times ans=0$$
$$ans=\frac B A$$
$$ans=\frac{\sum value_i\times x_i}{\sum cost_i\times x_i}$$
最小化就求最小生成树

例题：[POJ2728]Desert King

#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const double eqs=1e-6;
const int INF=0x3f3f3f3f;
struct point{
    double x,y,z;
}p[1100];
int vis[1100],n;
double dis[1100];
double f(int i,int j,double mid)
{return fabs(p[i].z-p[j].z)-mid*sqrt((p[i].x-p[j].x)*(p[i].x-p[j].x)+(p[i].y-p[j].y)*(p[i].y-p[j].y));}
double solve(double mid)
{
    int id,u;
    double ans=0,min1;
    memset(vis,0,sizeof vis);
    for(int i=0;i<n;++i)dis[i]=INF;
    vis[0]=1;dis[0]=0;u=0;
    for(int i=1;i<n;++i)
    {
        min1=INF;id=0;
        for(int j=0;j<n;++j)
        {
            if(vis[j])continue;
            dis[j]=min(dis[j],f(u,j,mid));
            if(min1-dis[j]>=eqs)
            {
                min1=dis[j];
                id=j ;
            }
        }
        ans+=min1;
        vis[id]=1;
        u=id;
    }
    return ans;
}
int main()
{
    double temp,max1,min1,l,r,mid;
    while(scanf("%d",&n)&&n)
    {
        l=r=0.0;
        max1=0;min1=INF;
        for(int i=0;i<n;++i)
        {
            scanf("%lf %lf %lf",&p[i].x,&p[i].y,&p[i].z);
            min1=min(min1,p[i].z);
            max1=max(max1,p[i].z) ;
        }
        r=(max1-min1)*n;
        while(r-l>eqs)
        {
            mid=(l+r)/2.0 ;
            temp=solve(mid);
            if(fabs(temp)<eqs)break;
            if(temp<0)
                r=mid;
            else    l=mid;
        }
        printf("%.3f\n",mid) ;
    }
    return 0;
}

问题模型3--最优比率环

给定有边权和点权的图，求一个环使得点权和与边权和的比值最大
解决方法：
套用01分数规划模型，点权为$value_i$，边权为$cost_i$，一个环为$C$
问题要求最大化$\frac{\sum value_i}{\sum cost_i},i\in C$
若答案为r*，那么对于任意一个环有

求最小化的时候

例题：[POJ3621] Sightseeing Cows

说明:为什么答案一定是简单环。
假设最优解是由两个环相交而来，设交点收益为a，两个环记作1,2。
有$\frac{v1+v2+a}{c1+c2}\gt\frac{a+v1}/{c1…(1)}$
$\frac{v1+v2+a}{c1+c2}\gt\frac{a+v2}/{2…(2)}$
化简得$c1v2\gt v1c2+ac2…(3)$
$c2v1\gt v2c1+ac1…(4)$
则$c1v2\gt v1c2+ac2\gt v1c2\gt v2c1+ac1\gt v2c1$，矛盾。
故答案一定是简单环。
所以就是个最优比率环

#include<queue>
#include<cmath>
#include<cstdio>
#include<cstring>
const double eps=1e-3;
int fir[1010],ne[5010],to[5010],cost[5010],val[1010],cnt[1010],m,n;
double dis[1010];
bool find(double x)
{
    std::queue<int> q;
    int p;
    for(int i=1;i<=n;++i)
        q.push(i);
    memset(cnt,0,sizeof(cnt));
    memset(dis,0,sizeof(dis));
    while(!q.empty())
    {
        p=q.front();
        q.pop();
        for(int i=fir[p];i;i=ne[i])
            if(x*cost[i]-val[to[i]]+dis[p]<dis[to[i]])
            {
                dis[to[i]]=x*cost[i]-val[to[i]]+dis[p];
                if(cnt[to[i]]==n-1)return 1;
                ++cnt[to[i]];
                q.push(to[i]);
            }
    }
    return 0;
}
void solve()
{
    double x,y,z,l,r,mid;
    l=0;r=1e6;
    while(r-l>=eps)
    {
        mid=(l+r)/2;
        if(find(mid))
            l=mid;
        else    r=mid;
    }
    if(l<eps)
        printf("0\n");
    else    printf("%.2f\n",l);
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i)
      scanf("%d",&val[i]);
    for(int x,i=1;i<=m;++i)
    {
        scanf("%d%d%d",&x,&to[i],&cost[i]);
        ne[i]=fir[x];
        fir[x]=i;
    }
    solve();
}