01分数规划练习

  • 时间:
  • 分类:

01分数规划

给一个集合$ S $，要求选取一个子集$ S' \subseteq S $，使得$$ \sum_{i \in S'} \frac{a_i}{b_i} $$取到最值。
不妨设最大值$ R = \sum_{i \in S'} \frac{a_i}{b_i} $，有$ 0 = \sum_{i \in S'} a_i - R \cdot b_i $。
考虑枚举该$ R $,对每一个确定的$ R $有确定的$ S' $，将该式值变量化并简记$ d_i=a_i-R \cdot b_i $，有
$$ F(R)=\sum_{i \in S'} a_i - R \cdot b_i=\sum_{i \in S'} d_i $$
(i)当$ F(R) > 0 $，则$S'$不变仍可存在一个$ R' > R $使得$ F(R')=0 $；
(ii)当$ F(R) < 0 $，则必然无法达到选取一个$ S' $使得$ F(R)=0 $，该$ R $无意义。
并且注意到$ d_i $随着$R$增而减，和式不破坏单调性，故$ F $单减。单调性存在，可以二分。
至此理论准备阶段结束。
还有一个问题是关于$ S' $的选取，这个是基于当前$ R $状态决定的，需根据题目具体分析。
把$ a,b $分别看成收益代价，不严谨地说，上面最化的就是性价比了。

POJ 2976

题

在一个n个有收益代价的数集合中取掉k个数，问剩下的数的性价比最大多少，答案乘100后四舍五入。

解

性价比如上所述就是二分。
对于每一种状态，求出$ d $后排序。因为$ d $值大的必然贡献性价比多，所以直接舍掉前$ k $小的。

码（47ms, 352K）

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
template<class T> 
inline void read(T& x)
{
    char c = getchar(); T p = 1, n = 0;
    while(c < '0' || c > '9'){if(c == '-') p = -1; c = getchar();}
    while(c >= '0' && c <= '9'){n = n * 10 + c - '0'; c = getchar();}
    x = p * n;
}
template<class T, class U>
inline void read(T& x, U& y){read(x), read(y);}
template<class T, class U, class V>
inline void read(T& x, U& y, V& z){read(x), read(y), read(z);}
const double eps = 1e-7;
const int maxn = 1e3 + 100;
int a[maxn], b[maxn];
double d[maxn];
int main()
{
    int n, k;
    while(read(n, k), n || k)
    {
        for(int i = 0; i < n; i++) read(a[i]);
        for(int i = 0; i < n; i++) read(b[i]);
        double l = 0.0, r = 1.0, m;
        while(r - l > eps)
        {
            m = (l + r) / 2.0;
            for(int i = 0; i < n; i++) d[i] = (double)a[i] - m * (double)b[i];
            sort(d, d + n);
            double R = 0.0;
            for(int i = k; i < n; i++) R += d[i];
            if(R > 0) l = m;
            else r = m;
        }
        printf("%.0f\n", m * 100);
    }
    return 0;
}

POJ 2728

题

求最小比率生成树。费用是高度差，距离是欧式距离。

解

二分套Prim……
神tmPrim都不会写了硬是写到TLE（摔
以及%.3lf会WA然后%.3f可以A哪位老司机可以解释一下？？？
然后其实可以不用二分，迭代也可以。（不动点理论？？）
因为对一个$ R $算出确定比值后比当前值大或小都可以迭代移动。
然后可以知道比$ R_{ans} $大的返回的值小于$ R $，否则大于$ R $，也就是说若干次迭代之后相同的一定是$ R_{ans} $。（就是上面性质(i)(ii)的简单变形）

码

二分（1797ms, 23992K）

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <cmath>
#define sqr(a) ((a) * (a))
using namespace std;
template<class T> 
inline void read(T& x)
{
    char c = getchar(); T p = 1, n = 0;
    while(c < '0' || c > '9'){if(c == '-') p = -1; c = getchar();}
    while(c >= '0' && c <= '9'){n = n * 10 + c - '0'; c = getchar();}
    x = p * n;
}
template<class T, class U>
inline void read(T& x, U& y){read(x), read(y);}
template<class T, class U, class V>
inline void read(T& x, U& y, V& z){read(x), read(y), read(z);}
const double eps = 1e-7, INF = 10000000;
const int maxn = 1e3 + 1000;
double a[maxn], b[maxn], c[maxn];
bool visit[maxn];
double dis[maxn][maxn], cost[maxn][maxn], low[maxn];
int fa[maxn];
int n;
double MST(double m)
{
    double sum = 0;
    for(int i = 1; i <= n; i++)
        fa[i] = 1, low[i] = cost[1][i] - m * dis[1][i];
    fa[1] = -1;
    for(int i = 1; i < n; i++)
    {
        int v = -1; double mi = INF;
        for(int j = 1; j <= n; j++) if(~fa[j] && low[j] < mi)
            v = j, mi = low[j];
        if(~v)
        {
            fa[v] = -1;
            sum += low[v];
            for(int j = 1; j <= n; j++)
            {
                double tmp = cost[v][j] - m * dis[v][j];
                if(~fa[j] && tmp < low[j])
                    low[j] = tmp, fa[j] = v;
            }
        }
    }
    return sum;
}
int main()
{
    while(read(n), n)
    {
        for(int i = 1; i <= n; i++)
        {
            scanf("%lf%lf%lf", &a[i], &b[i], &c[i]);
            for(int j = 1; j < i; j++)
                dis[i][j] = dis[j][i] = sqrt(sqr(a[i]-a[j])+sqr(b[i]-b[j])),
                cost[i][j] = cost[j][i] = abs(c[i]-c[j]);
        }
        double L = 0.0, R = 100000.0, M;
        while(R - L > eps)
        {
            M = (L + R) / 2.0;
            if(MST(M) >= 0) L = M;
            else R = M;
        }
        printf("%.3f\n", M);
    }
}

迭代（235ms, 23992K）

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <cmath>
#define sqr(a) ((a) * (a))
using namespace std;
template<class T> 
inline void read(T& x)
{
    char c = getchar(); T p = 1, n = 0;
    while(c < '0' || c > '9'){if(c == '-') p = -1; c = getchar();}
    while(c >= '0' && c <= '9'){n = n * 10 + c - '0'; c = getchar();}
    x = p * n;
}
template<class T, class U>
inline void read(T& x, U& y){read(x), read(y);}
template<class T, class U, class V>
inline void read(T& x, U& y, V& z){read(x), read(y), read(z);}
const double eps = 1e-7, INF = 10000000;
const int maxn = 1e3 + 1000;
double a[maxn], b[maxn], c[maxn];
bool visit[maxn];
double dis[maxn][maxn], cost[maxn][maxn], low[maxn];
int fa[maxn];
int n;
double MST(double m)
{
    double co = 0, distance = 0;
    for(int i = 1; i <= n; i++)
        fa[i] = 1, low[i] = cost[1][i] - m * dis[1][i];
    fa[1] = -1;
    for(int i = 1; i < n; i++)
    {
        int v = -1; double mi = INF;
        for(int j = 1; j <= n; j++) if(~fa[j] && low[j] < mi)
            v = j, mi = low[j];
        if(~v)
        {
            co += cost[fa[v]][v]; distance += dis[fa[v]][v];
            fa[v] = -1;
            for(int j = 1; j <= n; j++)
            {
                double tmp = cost[v][j] - m * dis[v][j];
                if(~fa[j] && tmp < low[j])
                    low[j] = tmp, fa[j] = v;
            }
        }
    }
    return co / distance;
}
int main()
{
    while(read(n), n)
    {
        for(int i = 1; i <= n; i++)
        {
            scanf("%lf%lf%lf", &a[i], &b[i], &c[i]);
            for(int j = 1; j < i; j++)
                dis[i][j] = dis[j][i] = sqrt(sqr(a[i]-a[j])+sqr(b[i]-b[j])),
                cost[i][j] = cost[j][i] = abs(c[i]-c[j]);
        }
        double L = 0.0, R = 0.0;
        while(true)
        {
            L = MST(R);
            if(fabs(R - L) < eps) break;
            R = L;
        }
        printf("%.3f\n", L);
    }
}

标签: 01分数规划

添加新评论