算法数学算法

01分数规划

字数统计: 1.9k字   |   阅读时长: 8分
, ,

摘要: 01分数规划，算法与例题

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

01分数规划模型

问题

01分数规划是指，给定整数 $a_{1}, a_{2}, a_{3}, …, a_{n}$，以及 $b_{1}, b_{2}, b_{3}, …, b_{n}$，求一组解 $x_{i}, 1 \leq x \leq n, x_{i} \in \{0, 1\}$。使得下式最大化

相当于给定 n 对整数 $(a_{i}, b_{i}), i = 1,2,…,n$，从中选出若干对，使得选出的数对中 a 之和与 b 之和的商最大

分析

记 $\frac{\sum_{i=1}^{n}a_{i}x_{i}}{\sum_{i=1}^{n}b_{i}x_{i}}$ 的最大值为 $\xi$：$\frac{\sum_{i=1}^{n}a_{i}x_{i}}{\sum_{i=1}^{n}b_{i}x_{i}} \leq \xi$。

直接求 $\xi$ 很难，但是如果给定一个 $L$，如果能够快速回答 $\frac{\sum_{i=1}^{n}a_{i}x_{i}}{\sum_{i=1}^{n}b_{i}x_{i}} \geq L$ 是否成立，就可以考虑值域二分的办法。

  • 若成立，则 L 是答案，但是有可能存在比 L 更大的值是答案，后续只需要确认 $\geq L$ 的值
  • 若不成立，则 L 不是答案，比 L 大的更不可能是答案，后续只需要确认 $< L$ 的值

问题变成了给定 L，$\frac{\sum_{i=1}^{n}a_{i}x_{i}}{\sum_{i=1}^{n}b_{i}x_{i}} \geq L$ 是否成立。等价于问是否存在一组 $\{x_{1},x_{2},…,x_{n}\}$，使得 $\sum_{i=1}^{n}(a_{i} - Lb_{i})x_{i} \geq 0$，只需要判定 $\sum_{i=1}^{n}(a_{i} - Lb_{i})x_{i}$ 的最大值是否非负。

问题变成了求 $\sum_{i=1}^{n}(a_{i} - Lb_{i})x_{i}$ 的最大值。这个问题就是从 n 个数 $a_{i} - Lb_{i}, i=1,2,…,n$ 中选出若干个使得和最大。直接把所有正数选出来就可以了。

算法

1
2
3
4
5
6
7
8
9
10
left = (double)INT_MIN, right = (double)INT_MAX
while(left + eps < right)
{
    int mid = (left + right) / 2;
    if(check(mid))
        left = mid;
    else
        right = mid;
}
return left;

check 中判断 $a_{i} - mid * b_{i}$ 中所有正数的和是否大于等于 0.

01分数规划的应用 — 最优比率生成树

01 分数规划经常与图论有所结合。比如最优比率生成树的问题，问题如下：

N 个点，M 条边的无向图，每条边 i 有一个收益 c[i] 和一个成本 r[i]，求一个生成树，使得各边收益之和除以成本之和最大。

做法就是之前提到的值域二分，在二分的 check 函数中重建图执行最大生成树，重建图时，边权为 $c[i] - mid * r[i]$。若最大生成树的权值和非负，则 l = mid，否则 r = mid。

下面我们通过 01 分数规划的值域二分算法解决一个 acwing 上的题目，与最优比率生成树问题几乎一样。此外在 负环 中的例题，也是一个 01 分数规划的问题，也可以参考。

题目

国王决定在全国各地建立渠道，为每个村庄提供水源。

与首都相连的村庄将得到水资源的浇灌。

他希望构建的渠道可以实现单位长度的平均成本降至最低。

换句话说，渠道的总成本和总长度的比值能够达到最小。

他只希望建立必要的渠道，为所有的村庄提供水资源，这意味着每个村庄都有且仅有一条路径连接至首都。

由于任意两个村庄的高度均不同，所以每个渠道都需要安装一个垂直的升降机，从而使得水能够上升或下降。

建设渠道的成本只跟升降机的高度有关，换句话说只和渠道连接的两个村庄的高度差有关。

需注意，所有村庄（包括首都）的高度都不同，不同渠道之间不能共享升降机。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
输入格式
输入包含多组测试数据。
每组测试数据第一行包含整数 N，表示村庄（包括首都）的总数目。
接下来 N 行，每行包含三个整数 x，y，z，描述一个村庄的地理位置，(x,y) 为该村庄的位置坐标，z 为该村庄的地理高度。
第一个被描述的村庄即为首都。
当输入一行为 0 时，表示输入终止。

输出格式
每组数据输出一个结果，每个结果占一行。
结果为一个保留三位小数的实数，表示渠道的总成本和总长度的比值的最小值。

数据范围
2<=N<=1000,
0<=x,y<10000,
0<=z<=10000000

输入样例：
4
0 0 0
0 1 1
1 1 2
1 0 3
0
输出样例：
1.000

算法：01分数规划

每条边 i 有一个长度 dist[i] 和一个成本 cost[i]，求生成树，使得单位长度的成本最小。

值域二分，check 中重建图执行最小生成树，重建图时边权为 $cost[i] - mid * dist[i]$，若最小生成树的权值和非负，则 r = mid，否则 l = mid

注意：重建图时，邻接表需要填入双向边。

以下代码逻辑没问题，但是建图等地方求有些冗余计算需要优化，尽量显式不建图，否则会超时。

代码 (C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <climits>
#include <cmath>
#include <iomanip>

using namespace std;

const double eps = 1e-9;

struct Edge
{
    int v;
    double w;
    Edge(int v, double w):v(v),w(w){}
};

struct Cmp
{
    bool operator()(const Edge& e1, const Edge& e2) const
    {
        return e1.w > e2.w;
    }
};

double mst(const vector<vector<Edge>>& g)
{
    int N = g.size();
    vector<bool> visited(N, false);
    priority_queue<Edge, vector<Edge>, Cmp> pq;
    pq.push(Edge(0, 0.0));
    double cost = 0.0;
    while(!pq.empty())
    {
        Edge e = pq.top();
        pq.pop();
        if(visited[e.v])
            continue;
        visited[e.v] = true;
        cost += e.w;
        for(Edge son: g[e.v])
        {
            if(visited[son.v])
                continue;
            pq.push(son);
        }
    }
    for(int v: visited)
        if(!v)
            return -1;
    return cost;
}

struct Point
{
    int x, y, z;
    Point(int x, int y, int z):x(x),y(y),z(z){}
};

struct EdgeInfo
{
    double cost;
    double dist;
    EdgeInfo(double c, double d):cost(c),dist(d){}
};

bool check(double mid, const vector<vector<EdgeInfo>>& edgeinfos)
{
    int N = edgeinfos.size();
    vector<vector<Edge>> g(N);
    for(int i = 0; i < N - 1; ++i)
        for(int j = i + 1; j < N; ++j)
        {
            double w = edgeinfos[i][j].cost - mid * edgeinfos[i][j].dist;
            g[i].emplace_back(j, w);
            g[j].emplace_back(i, w);
        }
    double ans = mst(g);
    return ans + eps < 0;
}

int main()
{
    int N;
    while(cin >> N && N > 0)
    {
        vector<Point> points;
        for(int i = 0; i < N; ++i)
        {
            int x, y, z;
            cin >> x >> y >> z;
            points.emplace_back(x, y, z);
        }
        vector<vector<EdgeInfo>> edgeinfos(N, vector<EdgeInfo>(N, EdgeInfo(-1, -1)));
        for(int i = 0; i < N - 1; ++i)
            for(int j = i + 1; j < N; ++j)
            {
                edgeinfos[i][j].cost = abs(points[i].z - points[j].z);
                edgeinfos[i][j].dist = sqrt(pow(abs(points[i].x - points[j].x), 2) + pow(abs(points[i].y - points[j].y), 2));
            }
        double left = 0.0, right = (double)1e9;
        while(left + eps < right)
        {
            double mid = (left + right) / 2;
            if(check(mid, edgeinfos))
                right = mid;
            else
                left = mid;
        }
        cout << setiosflags(ios::fixed) << setprecision(3);
        cout << left << endl;
    }
}
Share