分数规划算法

前言

在写 SPFA 判负环的时候发现很多题目需要联系到高贵的0/1分数规划，但是截至当时我还没有学这样优雅的算法，故先将咕一咕，把关于分数规划的东西弄清楚再回去填坑。正好刚考完高一下的合格考，觉得正是适合学新东西的时候，在此归纳一些简单的分数规划知识……~~这都什么跟什么啊~~

分数规划基本模型如下：

给出有个元素的两个数列和，求对整数，使得下式最大化：

通俗一点地说，给出件商品。每件商品都有一个价格和价值，你需要做的就是求出买哪些商品能够让所有物品总的性价比最高——即最优购买问题。

一般分数规划问题还会有一些奇怪的限制，比如『分母至少为』。

——OI WIKI

分数规划求解

我们假设当前有一个值，假定当前的并非最优解，那么一定会有如下特殊情况：

也就是说存在组合使最后一个不等式成立时，就不是最大值，也就是比答案小；反之，将大于号反向，就比答案大。我们就可以二分值，不断检测上面的不等式情况，收缩二分区间。

代码：

const double EPS = 1e-6;

bool check(double d) {
    double res = 0;
    for (int i = 1; i <= n; i++) {
        if (a[i] - d * b[i] > 0) res += a[i] - d * b[i];
    }
    return res >= 0;
}

int main() {
    cin >> n >> k;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) cin >> b[i];

    double L = 0, R = INFINITY;
    while (R - L > EPS) {
        double mid = (L + R) / 2;
        if (check(mid)) L = mid;
        else R = mid;
    }
    cout << L << endl;
    return 0;
}

很多时候分数规划的题目都会直接间接地把物品的权值变为，因此二分即可求解。

分数规划例题

洛谷 P10505 Dropping Test

题目地址：P10505

题目难度：普及/提高-

在某个课程中，你需要进行次测试。

如果你在共计道题的测试上的答对题目数量为，你的累积平均成绩就被定义为

给定您的考试成绩和一个正整数，如果您被允许放弃任何门考试成绩，您的累积平均成绩的可能最大值是多少。

假设您进行了次测试，成绩分别为和。

在不放弃任何测试成绩的情况下，您的累积平均成绩是。

然而，如果你放弃第三门成绩，则您的累积平均成绩就变成了。

输入格式：

输入包含多组测试用例，每个测试用例包含三行。

对于每组测试用例，第一行包含两个整数和。

第二行包含个整数，表示所有的。

第三行包含个整数，表示所有的。

当输入用例时，表示输入终止，且该用例无需处理。

输出格式：

对于每个测试用例，输出一行结果，表示在放弃门成绩的情况下，可能的累积平均成绩最大值。

结果应四舍五入到最接近的整数。

数据范围：

数据范围 , , 。

这道题结合了分数规划和贪心。我们的目标是让的值最大。先预处理所有的，并对它排序，每次取最大的个累加。判断得到的结果是否大于等于即可。

#include <bits/stdc++.h>
#define N 1010
using namespace std;

double a[N], b[N];
double arr[N];
const double EPS = 1e-6;
int n, k;

bool check(double d) {
    double res = 0;
    for (int i = 1; i <= n; i++) arr[i] = a[i] - d * b[i];
    sort(arr + 1, arr + 1 + n);
    for (int i = n; i > k; i--) {
        res += arr[i];
    }
    return res >= 0;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    while (cin >> n >> k, n || k) {
        for (int i = 1; i <= n; i++) cin >> a[i];
        for (int i = 1; i <= n; i++) cin >> b[i];
        double L = 0, R = 1;
        while (R - L > EPS) {
            double mid = (L + R) / 2;
            if (check(mid)) L = mid;
            else R = mid;
        }
        cout << round(100 * L) << endl;
    }
    return 0;
}

由于涉及到浮点数二分，我们需要定义一个浮点数精确度来近似处理，一般来说不会大于。

洛谷 P4377 [USACO18OPEN] Talent Show G

题目地址：P4377

题目难度：提高+/省选-

题目来源：USACO 2018

Farmer John 要带着他的头奶牛，方便起见编号为，到农业展览会上去，参加每年的达牛秀！他的第头奶牛重量为，才艺水平为，两者都是整数。

在到达时，Farmer John 就被今年达牛秀的新规则吓到了：

（一）参加比赛的一组奶牛必须总重量至少为（这是为了确保是强大的队伍在比赛，而不仅是强大的某头奶牛），并且。

（二）总才艺值与总重量的比值最大的一组获得胜利。

FJ 注意到他的所有奶牛的总重量不小于，所以他能够派出符合规则（一）的队伍。帮助他确定这样的队伍中能够达到的最佳的才艺与重量的比值。

输入格式：

第一行是两个整数，分别表示牛的个数和总重量限制。

第到行，每行两个整数，第行的整数表示第头奶牛的重量和才艺水平。

输出格式：

请求出 Farmer 用一组总重量最少为的奶牛最大可能达到的总才艺值与总重量的比值。

如果你的答案是，输出向下取整的值，以使得输出是整数（当问题中的数不是一个整数的时候，向下取整操作在向下舍入到整数的时候去除所有小数部分）。

请注意当问题的答案恰好是整数时，你的程序可能会由于浮点数精度误差问题最后得到一个的答案，向下取整后变为导致答案错误。这种情况下你可以在输出答案前给答案加上一个极小的值来避免该问题。

数据范围：

对于全部的测试点，保证，，，。

这道题结合了01背包和01分数规划。这里的限制提醒我们需要用背包解决，根据分数规划的二分判别式，我们把每头牛的价值重新赋为，在每次二分过程中都会改变。对于当前二分到的每个值，都做一次01背包。dp[i] 的含义是“总重量为的牛的最大规划价值（判别式的最大值）”，对于每头牛，就有两种情况：

选择这头牛：数据更新为“不选这头牛的最大价值加上当前牛的价值”，即。
不选这头牛：数据不更新，即。
若，直接结算到总重量为的情况。

也就是说每次二分得到一个中值，然后对每个中值跑背包算法即可。为了避免一些奇奇妙妙的浮点数误差，输入时统一将才艺水平乘，对应下来二分的上下界也要乘。

#include <bits/stdc++.h>
#define N 300
#define M 1010

using namespace std;
typedef long long ll;

struct Cow {
	int talent, weight;
	ll w;
} cow[N];
int n, W;
ll dp[M];

bool check(ll d) {
	for (int i = 1; i <= n; i++) {
		cow[i].w = cow[i].talent - d * cow[i].weight;
	}
	dp[0] = 0;
	for (int i = 1; i <= W; i++) {
		dp[i] = -1e10;
	}
	for (int i = 1; i <= n; i++) {
		for (int j = W; j >= 0; j--) {
			dp[min(W, j + cow[i].weight)] = max(dp[min(W, j + cow[i].weight)], dp[j] + cow[i].w);
		}
	}
	return dp[W] >= 0;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	cin >> n >> W;
	ll sum = 0;
	for (int i = 1; i <= n; i++) {
		int w, t;
		cin >> w >> t;
		sum += t * 1000;
		cow[i].talent = t * 1000;
		cow[i].weight = w;
	}
	ll L = 0, R = sum;
	while (R >= L) {
		ll mid = (L + R) >> 1;
		if (check(mid)) L = mid + 1;
		else R = mid - 1;
	}
	cout << L - 1 << endl;
	return 0;
}

当然还有一种的做法，由 DengDuck 提出。其中提到了“糖水不等式”：

我们都知道，向水中放糖会让水变甜。如果放糖前水的总体积为，溶质（糖）的体积为，放入糖的体积为。根据生活经验有，即糖水变甜。推论：。

博客地址

洛谷 P3199 [HNOI2009] 最小圈

题目地址：P3199

题目难度：省选/NOI-

题目来源：各省省选湖南 2009

考虑带权有向图以及，每条边（，）的权值定义为。设。

（）是中的一个圈当且仅当（）和都在中。称为圈的长度，同时记，并定义圈的平均值为

即上所有边的权值的平均值。设为中所有圈的平均值的最小值。

给定图以及，求出中所有圈的平均值的最小值。

输入格式：

第一行两个正整数，分别为和，并用一个空格隔开。其中，分别表示图中有个点和条边。

接下来行，每行三个数，表示有一条边且该边的权值为，注意边权可以是实数。输入数据保证图连通，存在圈且有一个点能到达其他所有点。

输出格式：

一个实数，要求精确到小数点后位。

数据范围：

对于的数据，，，，且。

提示：本题存在的做法，但是的做法也可以通过。

本题的做法来源于在1977年发布的一篇题为《有向图最优环比率的特征》的论文。其中他描述的算法被称作算法，能够在的复杂度内求解该问题，而且是正解。~~但是我不会这个算法~~，这里仅介绍的做法，也就是分数规划的解法。

根据题意，我们要求分式的最小值。也就是找到一个环，使得环上边权之和与环中点数之商最大。接续分数规划的思路，我们先来化简这个式子：假设当前二分到，且它不是最小值，因此存在数据满足。接下来去分母得。考虑到当前环中有个点，严格来说上式应为。移项展开得，即。

这下非常明朗了：对于每次二分，假设我们把边权重新设为。根据化简的式子可得，我们需要求出一个环，环上所有边的边权均重设为，并满足重设后的边权之和小于等于。就可以转化为求负环的问题了。如果存在负环，代表最初假设成立，最终答案应小于，收缩右区间；否则收缩左区间。注意到边权为实数，可正可负，极端情况下，环的均值可以达到，二分的左右区间就是和。要求答案保留八位小数，浮点数精度的设置不宜大于。

#include <bits/stdc++.h>

#define N 3010
#define M 100010

using namespace std;

struct Edge {
    int to, ne;
    double w;
} edges[M];
const double EPS = 1e-9;
int h[N], cnt[N], idx = 0;
double dist[N];
bool st[N];
int n;

void add(int u, int v, double w) {
    idx++;
    edges[idx].to = v;
    edges[idx].ne = h[u];
    edges[idx].w = w;
    h[u] = idx;
}

bool check(double d) {
    memset(cnt, 0, sizeof cnt);
    memset(st, false, sizeof st);
    for (int i = 1; i <= n; i++) dist[i] = INT_MAX;

    queue<int> q;
    for (int i = 1; i <= n; i++) {
        q.push(i);
        st[i] = true;
        dist[i] = 0;
    }

    while (!q.empty()) {
        int id = q.front();
        q.pop();

        st[id] = false;
        for (int i = h[id]; ~i; i = edges[i].ne) {
            int j = edges[i].to;
            double wfp = edges[i].w - d;
            if (dist[j] > dist[id] + wfp) {
                dist[j] = dist[id] + wfp;
                cnt[j] = cnt[id] + 1;
                if (cnt[j] == n) return true;
                if (!st[j]) {
                    q.push(j);
                    st[j] = true;
                }
            }
        }
    }
    return false;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    memset(h, -1, sizeof h);

    int m;
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int a, b;
        double c;
        cin >> a >> b >> c;
        add(a, b, c);
    }
    double L = -1e7, R = 1e7;
    while (R - L > EPS) {
        double mid = (L + R) / 2;
        if (check(mid)) R = mid;
        else L = mid;
    }
    cout << fixed << setprecision(8) << L << endl;

    return 0;
}

POJ 2728 Desert King

题目地址：POJ 2728

伟大的呆娃 David 刚刚成为沙漠王国的国王。为了巩固他的统治，他准备在王国内修建很多连通每座城市的灌溉水渠。作为王国的统治者兼吉祥物，他需要用一种最优的方式修建这些水渠……

经过几天的实地调研，他想到了一个修建方案：他想要最小化单位长度内的修建成本。换句话说，修建的总成本与总长度的比值需要最小。他只需修建必要的水渠，因此连接到某个城市的水渠只有唯一一条到达王宫的可行路径。

他的御用工程师们测量了每个城市的位置与海拔高度。每条水渠必须笔直地连通两个城市，且没有坡度。但是两座城市之间又可能存在高度差，因此他们决定在某两座城市之间修建一个垂直运水机，它可以垂直地运送水资源。水渠的长度定义为两座城市之间的水平距离、其修建成本定义为垂直运水机的竖直高度。需要注意的是：任意两座城市的高度都是不同的，且不同的水渠不能共用一个垂直运水机。水渠之间允许交叉，且任意三座城市不共线。

作为呆娃 David 的御用科学家和 OIer，你被要求求出符合要求的最小比值。

输入格式：

多组测试数据，每组数据的第一行有一个整数，代表城市总数。

接下来行，每行三个数，代表每座城市的三维坐标。第一座城市是王宫所在地。

时结束读入

输出格式：

对于每组数据，输出一行代表最优比率，保留三位小数

数据范围：

，，

题目翻译 By 我

这是一道最优比率生成树的题目。题目要求最小化，熟练地推出如下式子：，当该式子成立时代表还可以收缩左区间。

接下来，我们预处理规划权值，然后对于邻接矩阵的稠密图，跑一遍~~我个人蛮不想用的~~Prim算法（甚至Prim没有加高贵的和首尾空格，可见作者的不情愿使用之情），返回最小比率生成树的权值是否非负即可。注意到保留三位小数，精度理论上不应大于数量级。

#include <iostream>
#include <iomanip>
#include <cmath>
#include <cstring>

#define N 1010
using namespace std;

struct Village {
    double x, y, z;
} villages[N];
const double EPS = 1e-6;
double dist[N][N], budget[N][N];
double prim[N];
bool st[N];
int n;
double sum = 0;

double dis(Village i, Village j) {
    return sqrt(pow(i.x - j.x, 2) + pow(i.y - j.y, 2));
}

void init() {
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j < i; j++) {
            dist[i][j] = dist[j][i] = dis(villages[i], villages[j]);
            budget[i][j] = budget[j][i] = fabs(villages[i].z - villages[j].z);
            sum += budget[i][j];
        }
    }
}

bool check(double d) {
    memset(st, false, sizeof st);

    double tmp = 0;
    for (int i = 1; i <= n; i++) prim[i] = budget[1][i] - d * dist[1][i];
    st[1] = true;

    for (int i = 1; i <= n; i++) {
        int t = -1;
        double minx = INT_MAX;
        for (int j = 1; j <= n; j++) {
            if (!st[j] && minx > prim[j]) {
                t = j;
                minx = prim[j];
            }
        }
        if (t == -1 || minx >= INT_MAX) break;
        st[t] = true;
        tmp += minx;
        for (int j = 1; j <= n; j++) {
            double wfp = budget[t][j] - d * dist[t][j];
            if (!st[j] && prim[j] > wfp) {
                prim[j] = wfp;
            }
        }
    }
    return tmp >= 0;
}

int main() {
    while (cin >> n, n) {
        sum = 0;
        for (int i = 1; i <= n; i++) {
            double x, y, z;
            cin >> x >> y >> z;
            villages[i].x = x;
            villages[i].y = y;
            villages[i].z = z;
        }
        init();
        double L = 0, R = sum;
        while (R - L > EPS) {
            double mid = (L + R) / 2;
            if (check(mid)) L = mid;
            else R = mid;
        }
        cout << fixed << setprecision(3) << L << endl;
    }
    return 0;
}

由于 POJ 的评测机编译不了万能头和转型式结构体赋值，甚至没有 nullptr，因而把一些最具有本人特色的代码给删除/修改了。望周知。