Bỏ qua

Fractional Programming

Quy hoạch phân số dùng để tìm cực trị của một phân thức. Mô tả hình thức: cho \(a_i\) và \(b_i\), tìm một bộ \(w_i\in\{0,1\}\) để tối thiểu hóa hoặc tối đa hóa

\[ \displaystyle\frac{\sum\limits_{i=1}^na_i\times w_i}{\sum\limits_{i=1}^nb_i\times w_i} \]

Hiểu nôm na: mỗi vật có hai trọng số \(a\) và \(b\), chọn một số vật sao cho \(\displaystyle\frac{\sum a}{\sum b}\) nhỏ nhất hoặc lớn nhất.

Các bài quy hoạch phân số thường có ràng buộc đặc biệt, ví dụ “mẫu số ít nhất là \(W\)”.

Giải

Chia đôi đáp án

Cách chung là chia đôi đáp án. Giả sử đáp án hiện tại là \(\textit{mid}\), thì một bộ \(\{w_i\}\) hợp lệ sẽ khiến tỉ số không nhỏ hơn \(\textit{mid}\). Lập bất đẳng thức và biến đổi:

\[ \displaystyle \begin{aligned} &\frac{\sum a_i\times w_i}{\sum b_i\times w_i}\ge mid\\ \Longrightarrow&\sum a_i\times w_i-mid\times \sum b_i\cdot w_i\ge 0\\ \Longrightarrow&\sum w_i\times(a_i-mid\times b_i)\ge 0 \end{aligned} \]

Chỉ cần tìm giá trị lớn nhất của vế trái. Nếu lớn hơn \(0\) thì \(mid\) khả thi, nếu không thì không. Khó nhất là làm sao tính \(\displaystyle \sum w_i\times(a_i-mid\times b_i)\) max/min.

Thuật toán Dinkelbach

Thuật toán Dinkelbach1 có ý tưởng: mỗi lần lấy đáp án vòng trước làm \(L\) mới, lặp cho tới khi hội tụ.

Ví dụ

LOJ 149 01 分数规划

Có \(n\) vật, mỗi vật có hai trọng số \(a\) và \(b\). Tìm \(w_i\in\{0,1\}\) sao cho đúng \(k\) giá trị là \(1\), tối đa hóa \(\displaystyle\frac{\sum a_i\times w_i}{\sum b_i\times w_i}\).

Lời giải

Lấy \(a_i-mid\times b_i\) làm trọng số của vật \(i\), tham lam chọn \(k\) vật có trọng số lớn nhất. Nếu tổng > 0 thì khả thi, ngược lại không khả thi.

参考代码 
 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
#include <algorithm>
#include <cstdio>
#include <functional>
using namespace std;

constexpr int N = 100000 + 10;
constexpr double eps = 1e-6;

int n, k;
int a[N], b[N];
double c[N];

bool check(double mid) {
  double s = 0;
  for (int i = 1; i <= n; i++) c[i] = a[i] - b[i] * mid;
  // 将权值从大到小排序
  sort(c + 1, c + n + 1, greater<double>());
  for (int i = 1; i <= k; ++i)  // 选择前 k 个物品
    s += c[i];
  return s >= 0;
}

int main() {
  scanf("%d %d", &n, &k);
  for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
  for (int i = 1; i <= n; ++i) scanf("%d", &b[i]);
  double L = 0, R = 1;
  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;
}
洛谷 4377 Talent Show G

Có \(n\) vật, mỗi vật có hai trọng số \(a\) và \(b\).

Cần chọn \(w_i\in\{0,1\}\) để tối đa hóa \(\displaystyle\frac{\sum w_i\times a_i}{\sum w_i\times b_i}\).

Yêu cầu \(\displaystyle\sum w_i\times b_i \geq W\).

Lời giải

Bài này thêm ràng buộc mẫu số ít nhất \(W\), nên không thể dùng tham lam như trên.

Dùng ba lô 0/1. Lấy \(b_i\) làm trọng lượng, \(a_i-mid\times b_i\) làm giá trị, bài toán thành ba lô. Khi đó \(dp[n][W]\) là giá trị lớn nhất.

Trong DP, trọng lượng có thể vượt \(W\), khi đó coi như \(W\).

参考代码 
 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
#include <algorithm>
#include <cstdio>
using namespace std;

constexpr int MAXN = 250 + 10;
constexpr int MAXW = 1000 + 10;
constexpr double eps = 1e-6;

int n, W;
int w[MAXN], t[MAXN];
double f[MAXW];

bool check(double mid) {
  double s = 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 + w[i]);
      f[k] = max(f[k], f[j] + t[i] - mid * w[i]);
    }
  return f[W] >= 0;
}

int main() {
  scanf("%d %d", &n, &W);
  double L = 0, R = 0;
  for (int i = 1; i <= n; ++i) {
    scanf("%d %d", &w[i], &t[i]);
    R += t[i];
  }
  while (R - L > eps) {
    double mid = (L + R) / 2;
    if (check(mid))
      L = mid;
    else
      R = mid;
  }
  printf("%d\n", (int)(L * 1000));
  return 0;
}
POJ2728 Desert King

Mỗi cạnh có hai trọng số \(a_i\) và \(b_i\), tìm cây khung \(T\) sao cho \(\displaystyle\frac{\sum_{e\in T}a_e}{\sum_{e\in T}b_e}\) nhỏ nhất.

Lời giải

Lấy \(a_i-mid\times b_i\) làm trọng số mỗi cạnh, khi đó cây khung nhỏ nhất là nghiệm. Do đồ thị đầy đủ, dùng Prim.

参考代码 
 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
56
57
#include <algorithm>
#include <cmath>
#include <cstdio>
using namespace std;

const int N = 1000 + 10;
const double eps = 1e-5;

int n;
double d[N][N], c[N][N], dis[N];
int x[N], y[N], z[N];
bool vis[N];

bool ok(double m) {
  double ans = 0;
  for (int i = 1; i <= n; i++) vis[i] = false;
  dis[1] = 0;
  for (int i = 2; i <= n; i++) dis[i] = 1e18;
  for (int i = 1; i <= n; i++) {
    double mn = 1e18;
    int pt = -1;
    for (int j = 1; j <= n; j++)
      if (!vis[j] && mn > dis[j]) {
        pt = j;
        mn = dis[j];
      }
    if (!~pt) break;
    vis[pt] = true;
    ans += mn;
    for (int j = 1; j <= n; j++)
      if (j != pt) dis[j] = min(dis[j], c[pt][j] - m * d[pt][j]);
  }
  return ans >= 0;
}

int main() {
  while (scanf("%d", &n) == 1) {
    if (n == 0) break;
    for (int i = 1; i <= n; i++) scanf("%d %d %d", &x[i], &y[i], &z[i]);
    for (int i = 1; i <= n; i++)
      for (int j = i + 1; j <= n; j++) {
        d[i][j] = d[j][i] =
            sqrt((x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j]));
        c[i][j] = c[j][i] = abs(z[i] - z[j]);
      }
    double l = 0, r = 10000000;
    while (r - l > eps) {
      double m = (l + r) / 2;
      if (ok(m))
        l = m;
      else
        r = m;
    }
    printf("%.3f\n", l);
  }
  return 0;
}
[HNOI2009] 最小圈

Mỗi cạnh có trọng số \(w\), tìm chu trình \(C\) sao cho \(\displaystyle\frac{\sum_{e\in C}w}{|C|}\) nhỏ nhất.

Lời giải

Lấy \(a_i-mid\) làm trọng số cạnh, chu trình có tổng nhỏ nhất là nghiệm.

Vì chỉ cần kiểm tra nhỏ hơn \(0\), nên chỉ cần phát hiện chu trình âm.

Bài này có thuật toán \(O(nm)\); nếu quan tâm xem bài viết này.

参考代码 
 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
#include <algorithm>
#include <cstdio>
#include <tuple>
#include <vector>
using namespace std;

constexpr int N = 3000 + 10;
constexpr double eps = 1e-9;

int n, m;
double dis[N];
vector<pair<int, double>> g[N];

bool check(double mid) {  // 如果有负环返回 true
  bool flag = false;
  dis[0] = 0;
  for (int i = 1; i <= n; ++i) dis[i] = 1e9;
  for (int t = 1; t <= n; ++t) {
    flag = false;
    for (int u = 0; u <= n; ++u)
      for (auto vw : g[u]) {
        int v;
        double w;
        tie(v, w) = vw;
        if (dis[v] > dis[u] + w - mid) {
          dis[v] = dis[u] + w - mid;
          flag = true;
        }
      }
    if (!flag) break;
  }
  return flag;
}

int main() {
  scanf("%d %d", &n, &m);
  for (int i = 1; i <= m; ++i) {
    int u, v;
    double w;
    scanf("%d %d %lf", &u, &v, &w);
    g[u].push_back({v, w});
  }
  for (int i = 1; i <= n; i++) g[0].push_back({i, 0});
  double L = -1e7, R = 1e7;
  while (R - L > eps) {
    double mid = (L + R) / 2;
    if (check(mid))
      R = mid;
    else
      L = mid;
  }
  printf("%.8lf\n", L);
  return 0;
}

Bài tập

Tài liệu tham khảo & chú thích

  1. Dinkelbach, Werner. "On nonlinear fractional programming." Management science 13.7 (1967): 492-498. ↩

Last updated on this page:, Update history
Found an error? Want to help improve? Edit this page on GitHub!
Contributors to this page:greyqz, Ir1d, hsfzLZH1, huaruoji, banglee13
All content on this page is provided under the terms of the CC BY-SA 4.0 and SATA license, additional terms may apply