AIOJ

Fractional programming finds the extremum of a fraction. Formally, given $a_i$ and $b_i$ , choose $w_i\in\{0,1\}$ to minimize or maximize

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

In plain terms, these problems are like choosing some items, each with two weights $a$ and $b$ , so that $\displaystyle\frac{\sum a}{\sum b}$ is minimized or maximized.

General fractional-programming problems may also impose special constraints, such as “the denominator is at least $W$ ”.

Solution

Binary search

The general method for fractional programming is binary search on the answer. Suppose the current midpoint is $\textit{mid}$ ; then a set of $\{w_i\}$ has transformed weight at least $\textit{mid}$ . Writing this condition as an inequality and rearranging gives

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

Thus, we only need to find the maximum value of the expression on the left-hand side.If the maximum is greater than $0$ , then $mid$ is feasible; otherwise it is infeasible.The main difficulty of fractional programming is finding $\displaystyle \sum w_i\times(a_i-mid\times b_i)$ the maximum or minimum value.

Dinkelbach algorithm

The general idea of the Dinkelbach algorithm¹ is to use the answer from the previous iteration as the new $L$ and iterate until the answer converges.

Examples

LOJ 149 01 Fractional Programming

There are $n$ items, each with two weights $a$ and $b$ . Choose a set $w_i\in\{0,1\}$ ，where $w_i$ has exactly $k$ entries equal to $1$ , maximizing $\displaystyle\frac{\sum a_i\times w_i}{\sum b_i\times w_i}$ .

Solution

Treat $a_i-mid\times b_i$ as the weight of item $i$ and greedily choose the $k$ items with the largest weights.If their weight sum is greater than $0$ , the midpoint is feasible; otherwise it is infeasible.

Reference code

#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 the weights in descending order
  sort(c + 1, c + n + 1, greater<double>());
  for (int i = 1; i <= k; ++i)  // Select the first k items
    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 is feasible, so the answer is greater than mid
      L = mid;
    else  // mid is infeasible, so the answer is smaller than mid
      R = mid;
  }
  printf("%.6lf\n", L);
  return 0;
}

Luogu 4377 Talent Show G

There are $n$ items, each with two weights $a$ and $b$ .

Choose a set $w_i\in\{0,1\}$ ，such that $\displaystyle\frac{\sum w_i\times a_i}{\sum w_i\times b_i}$ is maximized.

The constraint is $\displaystyle\sum w_i\times b_i \geq W$ ．

Solution

This problem adds the constraint that the denominator is at least $W$ , so the greedy algorithm from the previous example no longer applies.

Consider 0-1 knapsack. Let $b_i$ be the weight of item $i$ , and let $a_i-mid\times b_i$ be the value of item $i$ ; the problem then becomes a knapsack problem. Thus $dp[n][W]$ is the maximum value.

During the DP, the total item weight may exceed $W$ ; treat it as $W$ directly.

Reference code

#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

Each edge has two weights $a_i$ and $b_i$ ; find a spanning tree $T$ such that $\displaystyle\frac{\sum_{e\in T}a_e}{\sum_{e\in T}b_e}$ is minimized.

Solution

Treat $a_i-mid\times b_i$ as the weight of each edge; the minimum spanning tree then gives the minimum value.This problem asks for a minimum spanning tree in a complete graph, so use Prim's algorithm.

Reference code

#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] Minimum Cycle

Each edge has weight $w$ ; find a cycle $C$ such that $\displaystyle\frac{\sum_{e\in C}w}{|C|}$ is minimized.

Solution

Treat $a_i-mid$ as the edge weight; the minimum-weight cycle then gives the minimum value.

Since we only need to determine whether the minimum is less than $0$ , it is enough to determine whether the graph contains a negative cycle.

There is also an algorithm with complexity $O(nm)$ ; see this article if interested.

Reference code

#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) {  // Return true if there is a negative cycle
  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;
}

Exercises

References and notes

Footnotes

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