跳转至

分數規劃

分數規劃用來求一個分式的極值。

形象一點就是，給出 \(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\) 是可行的，否則不可行。

求最小值的方法和求最大值的方法類似，讀者不妨嘗試着自己推一下。

Dinkelbach 算法

Dinkelbach 算法的大概思想是每次用上一輪的答案當做新的 \(L\) 來輸入，不斷地迭代，直至答案收斂。

分數規劃的主要難點就在於如何求 \(\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\) 的物品即可得到最大值。

為了方便初學者理解，這裏放上完整代碼：

參考代碼 
 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
#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;
}

為了節省篇幅，下面的代碼只保留 check 部分。主程序和本題是類似的。

POJ2976 Dropping tests

有 \(n\) 個物品，每個物品有兩個權值 \(a\) 和 \(b\)。

你可以選 \(n-k\) 個物品 \(p_1,p_2,\cdots,p_{n-k}\)，使得 \(\displaystyle\frac{\sum a_{p_i}}{\sum b_{p_i}}\) 最大。

輸出答案乘 \(100\) 後四捨五入到整數的值。

把第 \(i\) 個物品的權值設為 \(a_i-mid\times b_i\)，然後選最大的 \(n-k\) 個即可得到最大值。

1
2
3
4
5
6
7
8
9
bool cmp(double x, double y) { return x > y; }

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; ++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\)。

本題多了分母至少為 \(W\) 的限制，因此無法再使用上一題的貪心算法。

可以考慮 01 揹包。把 \(b_i\) 作為第 \(i\) 個物品的重量，\(a_i-mid\times b_i\) 作為第 \(i\) 個物品的價值，然後問題就轉化為揹包了。

那麼 \(dp[n][W]\) 就是最大值。

一個要注意的地方：\(\sum w_i\times b_i\) 可能超過 \(W\)，此時直接視為 \(W\) 即可。（想一想，為什麼？）

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
double f[1010];

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}\) 最小。

把 \(a_i-mid\times b_i\) 作為每條邊的權值，那麼最小生成樹就是最小值，

代碼就是求最小生成樹，故省略。

[HNOI2009] 最小圈

每條邊的邊權為 \(w\)，求一個環 \(C\) 使得 \(\displaystyle\frac{\sum_{e\in C}w}{|C|}\) 最小。

把 \(a_i-mid\) 作為邊權，那麼權值最小的環就是最小值。

因為我們只需要判最小值是否小於 \(0\)，所以只需要判斷圖中是否存在負環即可。

另外本題存在一種複雜度 \(O(nm)\) 的算法，如果有興趣可以閲讀 這篇文章。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
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;
}

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

總結

分數規劃問題是一類既套路又靈活的題目，一般使用二分解決。

分數規劃問題的主要難點在於推出式子後想辦法求出 \(\displaystyle\sum w_i\times(a_i-mid\times b_i)\) 的最大值/最小值，而這個需要具體情況具體分析。

習題

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：greyqz, Ir1d, hsfzLZH1, huaruoji
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用