分数规划
分数规划用来求一个分式的极值。
形象一点就是,给出
另外一种描述:每种物品有两个权值
一般分数规划问题还会有一些奇怪的限制,比如『分母至少为
求解¶
分数规划问题的通用方法是二分。
假设我们要求最大值。二分一个答案
那么只要求出不等号左边的式子的最大值就行了。如果最大值比
求最小值的方法和求最大值的方法类似,读者不妨尝试着自己推一下。
分数规划的主要难点就在于如何求
实例¶
模板¶
有
个物品,每个物品有两个权值 n 和 a 。求一组 b ,最大化 w_i\in\{0,1\} 的值。 \displaystyle\frac{\sum a_i\times w_i}{\sum b_i\times w_i}
把
为了方便初学者理解,这里放上完整代码:
参考代码
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 | // =================================== // author: M_sea // website: http://m-sea-blog.com/ // =================================== #include <algorithm> #include <cmath> #include <cstdio> #include <cstdlib> #include <cstring> #include <iostream> using namespace std; inline int read() { int X = 0, w = 1; char c = getchar(); while (c < '0' || c > '9') { if (c == '-') w = -1; c = getchar(); } while (c >= '0' && c <= '9') X = X * 10 + c - '0', c = getchar(); return X * w; } const int N = 100000 + 10; const double eps = 1e-6; int n; double a[N], b[N]; inline bool check(double mid) { double s = 0; for (int i = 1; i <= n; ++i) if (a[i] - mid * b[i] > 0) // 如果权值大于 0 s += a[i] - mid * b[i]; // 选这个物品 return s > 0; } int main() { // 输入 n = read(); for (int i = 1; i <= n; ++i) a[i] = read(); for (int i = 1; i <= n; ++i) b[i] = read(); // 二分 double L = 0, R = 1e9; while (R - L > eps) { double mid = (L + R) / 2; if (check(mid)) // mid 可行,答案比 mid 大 L = mid; else // mid 不可行,答案比 mid 小 R = mid; } // 输出 printf("%.6lf\n", L); return 0; } |
为了节省篇幅,下面的代码只保留 check
部分。主程序和本题是类似的。
POJ2976 Dropping tests¶
有
个物品,每个物品有两个权值 n 和 a 。 b 你可以选
个物品 k ,使得 p_1,p_2,\cdots,p_k 最大。 \displaystyle\frac{\sum a_{p_i}}{\sum b_{p_i}} 输出答案乘
后四舍五入到整数的值。 100
把第
1 2 3 4 5 6 7 8 | inline bool cmp(double x, double y) { return x > y; } inline bool check(double mid) { int s = 0; for (int i = 1; i <= n; ++i) c[i] = a[i] - mid * b[i]; sort(c + 1, c + n + 1, cmp); for (int i = 1; i <= n - k + 1; ++i) s += c[i]; return s > 0; } |
洛谷 4377 Talent Show¶
有
个物品,每个物品有两个权值 n 和 a 。 b 你需要确定一组
,使得 w_i\in\{0,1\} 最大。 \displaystyle\frac{\sum w_i\times a_i}{\sum w_i\times b_i} 要求
。 \displaystyle\sum w_i\times b_i \geq W
本题多了分母至少为
可以考虑 01 背包。把
那么
一个要注意的地方:
1 2 3 4 5 6 7 8 9 10 | double f[1010]; inline bool check(double mid) { for (int i = 1; i <= W; i++) f[i] = -1e9; for (int i = 1; i <= n; i++) for (int j = W; j >= 0; j--) { int k = min(W, j + b[i]); f[k] = max(f[k], f[j] + a[i] - mid * b[i]); } return f[W] > 0; } |
POJ2728 Desert King¶
每条边有两个权值
和 a_i ,求一棵生成树 b_i 使得 T 最小。 \displaystyle\frac{\sum_{e\in T}a_e}{\sum_{e\in T}b_e}
把
代码就是求最小生成树,我就不放代码了。
[HNOI2009]最小圈¶
每条边的边权为
,求一个环 w 使得 C 最小。 \displaystyle\frac{\sum_{e\in C}w}{|C|}
把
因为我们只需要判最小值是否小于
另外本题存在一种复杂度
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 | inline int SPFA(int u, double mid) //判负环 { vis[u] = 1; for (int i = head[u]; i; i = e[i].nxt) { int v = e[i].v; double w = e[i].w - mid; if (dis[u] + w < dis[v]) { dis[v] = dis[u] + w; if (vis[v] || SPFA(v, mid)) return 1; } } vis[u] = 0; return 0; } inline bool check(double mid) { //如果有负环返回 true for (int i = 1; i <= n; ++i) dis[i] = 0, vis[i] = 0; for (int i = 1; i <= n; ++i) if (SPFA(i, mid)) return 1; return 0; } |
总结¶
分数规划问题是一类既套路又灵活的题目,一般使用二分解决。
分数规划问题的主要难点在于推出式子后想办法求出
习题¶
build本页面最近更新:,更新历史
edit发现错误?想一起完善? 在 GitHub 上编辑此页!
people本页面贡献者:greyqz, Ir1d, hsfzLZH1
copyright本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供,附加条款亦可能应用