From b1438d4b1f62c575f4d85a8846cf37eb488659cf Mon Sep 17 00:00:00 2001
From: Mout-sea <2582621015@qq.com>
Date: Sun, 4 Aug 2019 17:40:20 +0800
Subject: [PATCH] =?utf8?q?Update=20=E5=88=86=E6=95=B0=E8=A7=84=E5=88=92?=
MIME-Version: 1.0
Content-Type: text/plain; charset=utf8
Content-Transfer-Encoding: 8bit

---
 docs/misc/fractional-programming.md | 148 ++++++++++++++++++++++++++++--------
 1 file changed, 117 insertions(+), 31 deletions(-)

diff --git a/docs/misc/fractional-programming.md b/docs/misc/fractional-programming.md
index a203b3fb..179538fa 100644
--- a/docs/misc/fractional-programming.md
+++ b/docs/misc/fractional-programming.md
@@ -1,6 +1,6 @@
 分数规划用来求一个分式的极值。
 
-形象一点就是，给出 $a_i$ 和 $b_i$ ，求一组 $w_i\in[0,1]$ ，最小化或最大化
+形象一点就是，给出 $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}
@@ -8,6 +8,8 @@ $$
 
 另外一种描述：每种物品有两个权值 $a$ 和 $b$ ，选出若干个物品使得 $\displaystyle\frac{\sum a}{\sum b}$ 最小/最大。
 
+一般分数规划问题还会有一些奇怪的限制，比如『分母至少为 $W$ 』。
+
 ## 求解
 
 分数规划问题的通用方法是二分。
@@ -29,28 +31,112 @@ $$
 
 * * *
 
-分数规划的主要难点就在于如何求 $\displaystyle \sum w_i\times(a_i-mid\times b_i)$ 的最大值/最小值。下面通过一系列实例来讲解该式子的最大值/最小值的求法。
+分数规划的主要难点就在于如何求 $\displaystyle \sum w_i\times(a_i-mid\times b_i)​$ 的最大值/最小值。下面通过一系列实例来讲解该式子的最大值/最小值的求法。
 
 ## 实例
 
+### 模板
+
+> 有 $n$ 个物品，每个物品有两个权值 $a$ 和 $b$ 。求一组 $w_i\in[0,1]$ ，最大化 $\displaystyle\frac{\sum a_i\times w_i}{\sum b_i\times w_i}$ 的值。
+
+把 $a_i-mid\times b_i$ 作为第 $i$ 个物品的权值，贪心地选所有权值大于 $0$ 的物品即可得到最大值。
+
+为了方便初学者理解，这里放上完整代码：
+
+```cpp
+// ===================================
+//   author: M_sea
+//   website: http://m-sea-blog.com/
+// ===================================
+#include <algorithm>
+#include <iostream>
+#include <cstdlib>
+#include <cstring>
+#include <cstdio>
+#include <cmath>
+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​$ 后四舍五入到整数的值。
 
-如果 $a_i-mid\times b_i>0$ ，那么把 $w_i$ 设成 $1$ ，否则把 $w_i$ 设成 $0$ ，即可求出最大值。
+把第 $i​$ 个物品的权值设为 $a_i-mid\times b_i​$ ，然后选最大的 $k​$ 个即可得到最大值。
 
 ```cpp
-bool check(double mid) {
-  double sum = 0;
-  for (int i = 1; i <= n; ++i)
-    if (a[i] - mid * b[i] > 0) sum += a[i] - mid * b[i];
-  return sum > 0;
+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
 
-> 要求 $\displaystyle\sum w_i\times b_i \geq W​$ 的分数规划。
+> 有 $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$ 。
 
 本题多了分母至少为 $W​$ 的限制，因此无法再使用上一题的贪心算法。
 
@@ -63,13 +149,13 @@ bool check(double mid) {
 ```cpp
 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;
+    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;
 }
 ```
 
@@ -94,25 +180,25 @@ inline bool check(double mid) {
 ```cpp
 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] = 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;
+    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;
+    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;
 }
 ```
 
-- 
2.11.0