分数规划问题

本文主要是介绍分数规划问题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

分数规划

概念及解法
一些题目

概念及解法

引用自OI Wiki

分数规划用来求一个分式的极值。
形象一点就是，给出 $a_i$ 和 $b_i$ ，求一组 $w_i\in\{0,1\}$ ，最小化或最大化 $\displaystyle\frac{\sum\limits_{i=1}^na_i\times w_i}{\sum\limits_{i=1}^nb_i\times w_i}$
另外一种描述：每种物品有两个权值 a 和 b，选出若干个物品使得 $\displaystyle\frac{\sum a}{\sum b}$ 最小/最大。
一般分数规划问题还会有一些奇怪的限制，比如『分母至少为 W』。

分数规划问题的通用解法是二分。

假设要求最大值。二分一个答案 mid，然后推式子（为了方便少写了上下界）：
$\displaystyle \begin{aligned} &\frac{\sum a_i\times w_i}{\sum b_i\times w_i}>mid\\ \Longrightarrow&\sum a_i\times w_i-mid\times \sum b_i\cdot w_i>0\\ \Longrightarrow&\sum w_i\times(a_i-mid\times b_i)>0 \end{aligned}$
那么只要求出不等号左边的式子的最大值就行了。如果最大值比 0 要大，说明 mid 是可行的，否则不可行。
求最小值的方法和求最大值的方法类似。

一些题目

UVa12164/LA4412 The Great Game
这是一道综合了概率（马尔可夫链）、二分、dp的好题，也是我碰到的首个分数规划题目。

UVa11090 Going in Cycle!!
给定一个n个点m条边的加权有向图，求平均权值最小的回路。输入第一行为数据组数T。每组数据第一行为图的点数n和边数m（n≤50）。以下m行每行3个整数u, v, w，表示有一条从u到v的有向边，权值为w。输入没有自环。对于每组数据，输出最小平均值。如果无解，输出“No cycle found.”。

#include <iostream>
#include <iomanip>
#include <cstring>
using namespace std;#define INF 20000000
#define N 52
struct {int v; double w;} g[N][N]; int w[N][N], c[N], f[N], cnt[N], q[N*N], m, n, kase = 0; double d[N];bool cycle() {int head = 0, tail = n;for (int i=1; i<=n; ++i) cnt[i] = d[i] = 0, f[i] = 1, q[i-1] = i;while (head < tail) {int u = q[head++]; f[u] = 0;for (int i=0; i<c[u]; ++i) {int v = g[u][i].v; double d1 = d[u] + g[u][i].w;if (d[v] > d1) {d[v] = d1;if (++cnt[v] >= n) return true;if (!f[v]) q[tail++] = v, f[v] = 1;}}}return false;
}bool cycle(double x) {for (int u=1; u<=n; ++u) for (int i=0; i<c[u]; ++i) g[u][i].w -= x;bool r = cycle();for (int u=1; u<=n; ++u) for (int i=0; i<c[u]; ++i) g[u][i].w += x;return r;
}void solve() {memset(w, 31, sizeof(w)); memset(c, 0, sizeof(c));cin >> n >> m;int x = 0;while (m--) {int u, v, z; cin >> u >> v >> z; x = max(x, z);if (w[u][v] > INF) g[u][c[u]++].v = v;if (z < w[u][v]) w[u][v] = z;}for (int u=1; u<=n; ++u) for (int i=0; i<c[u]; ++i) g[u][i].w = w[u][g[u][i].v];if (cycle(x + 1e-3))  {double l = 0., r = x;while (l + 1e-3 < r) {double m = (l+r) / 2.;cycle(m) ? r = m : l = m;}cout << "Case #" << ++kase << ": " << l << endl;} else cout << "Case #" << ++kase << ": No cycle found." << endl;
}int main() {cout << fixed << setprecision(2);int t; cin >> t;while (t--) solve();return 0;
}

洛谷 P3705 [SDOI2017] 新生舞会

#include <iostream>
#include <iomanip>
#include <cstring>
using namespace std;#define INF 1e30
#define N 102
double slack[N], lx[N], ly[N], m; int a[N][N], b[N][N], pre[N], p[N], vis[N], n, clk;void bfs(int u) {for (int i=1; i<=n; ++i) pre[i] = 0, slack[i] = INF;int y = 0, yy = 0; p[0] = u;do {double d = INF; int x = p[y]; vis[y] = clk;for (int i=1; i<=n; ++i) if (vis[i] != clk) {double w = lx[x] + ly[i] - a[x][i] + m*b[x][i];if (slack[i] > w) slack[i] = w, pre[i] = y;if (slack[i] < d) d = slack[i], yy = i;}for (int i=0; i<=n; ++i) vis[i] == clk ? (lx[p[i]]-=d, ly[i] += d) : slack[i] -= d;y = yy;} while (p[y]);while (y) p[y] = p[pre[y]], y = pre[y];
}double km() {lx[0] = ly[0] = 0.; vis[0] = 0;for (int i=1; i<=n; ++i) {p[i] = 0; lx[i] = -INF; ly[i] = 0.; vis[i] = 0;for (int j=1; j<=n; ++j) lx[i] = max(lx[i], a[i][j] - m*b[i][j]);}for (int i=1; i<=n; ++i) bfs(clk = i);double cc = 0.;for (int i=1; i<=n; ++i) cc += a[p[i]][i] - m*b[p[i]][i];return cc;
}double solve() {for (int i=1; i<=n; ++i) for (int j=1; j<=n; ++j) cin >> a[i][j];for (int i=1; i<=n; ++i) for (int j=1; j<=n; ++j) cin >> b[i][j];double l = 0., r = 1e4, eps = 1e-8;while (l+eps <= r) {m = .5*(l+r);km() < 0. ? r = m-eps : l = m+eps; }return r;
}int main() {ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);cout << fixed << setprecision(6);while (cin >> n) cout << solve() << endl;return 0;
}