分数规划入门 - 洛谷保存站

### 分数规划与二分法

首先，什么是分数规划呢？

一般来说，分数规划会给你一串 $a_i$ 和 $b_i$，要求你给出一串最佳的 $w_i \in \{0,1\} $，使得 $ \large\frac{\sum\limits_{i=1}^{n} a_i \times w_i}{\sum\limits_{i=1}^{n} b_i \times w_i}$ 最大或最小。

当然，除了这些，题目一般还会有些其它限制。

接下来，我们该如何求解此类问题呢？

正常人一般会考虑贪心，但是由于答案由分子和分母两部分组成，所以贪心一般而言都是错的。

这时，我们可以使用二分法。

首先，我们求得一个答案 $mid$，接着我们要验证这个 $mid$ 是否可行。我们将式子推一下：

$\large\frac{\sum\limits_{i=1}^{n} a_i \times w_i}{\sum\limits_{i=1}^{n} b_i \times w_i} > mid$

$\Longrightarrow\sum\limits_{i=1}^{n} a_i \times w_i > mid \times \sum\limits_{i=1}^{n} b_i \times w_i$

$\Longrightarrow\sum\limits_{i=1}^{n} a_i \times w_i - mid \times \sum\limits_{i=1}^{n} b_i \times w_i > 0$

$\Longrightarrow\sum\limits_{i=1}^{n} w_i \times (a_i - mid \times b_i) > 0$

我们只需要判断不等式左边的式子，就可以看出当前答案 $mid$ 是否可行。

另说一句，除了二分法，还有一种方法叫 $Dinkelbach$ 算法，这里不过多讲解~~简称不会~~。

------------

### 分数规划与其他算法的结合

1. 当题目中出现形如**分母至少为 $W$** 这样的限制时，可以考虑使用背包。将 $a_i - mid \times b_i$ 视为价值，将 $mid \times b_i$ 视为体积，最后求 $dp_W$ 的最大值。

**注意：当 $mid \times b_i$ 大于 $W$ 时，直接将其视为 $W$。**

2. 当题目给了你一颗树时，考虑树形 $dp$ 或是最小/大生成树。

3. 当题目给出一个图时，可以考虑网络流。

------------

### 模板及习题

一些分数规划的板题：

[P4377 [USACO18OPEN] Talent Show G](https://www.luogu.com.cn/problem/P4377)（背包）

[P3199 [HNOI2009] 最小圈](https://www.luogu.com.cn/problem/P3199)（找环）

[P4322 [JSOI2016] 最佳团体](https://www.luogu.com.cn/problem/P4322)（树上背包）

[P3705 [SDOI2017] 新生舞会](https://www.luogu.com.cn/problem/P3705)（最小费用最大流）

最后放一个贪心的模板（摘自OI Wiki）：

```cpp
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
using namespace std;

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];

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;
}
```

正在渲染内容...