跳转至

分数规划⚓︎

分数规划（\text{Fractional Programming}）是一类优化问题，其目标函数是变量的分数形式。
其形式化表述是，给出 a_i 和 b_i，求一组 w_i\in\{0,1\}，最小化或最大化

\frac{\sum_{i=1}^{n} a_i \times w_i}{\sum_{i=1}^{n} b_i \times w_i}

01分数规划的核心：

  • 数据转化成结余表达式的形式，当确定一个比值 x，就能在最优决策下计算出结余和
  • 最终希望获得在最优决策下，当结余和最接近 0 时，x 的值最优
  • 最优决策判定：通常可以根据贪心选择、01背包、最小生成树等方法进行判定

常见应用：最大平均值（\forall b_i = 1）、最大性价比、最大比率等组合优化问题。

二分法求解⚓︎

分数规划问题可以通过二分法来求解。 设目标值为 mid，则问题转化为判断是否存在一组 w_i 使得

\frac{\sum_{i=1}^{n} a_i \times w_i}{\sum_{i=1}^{n} b_i \times w_i} \geq mid \\ \Longrightarrow \sum_{i=1}^{n} a_i \times w_i \geq mid \times \sum_{i=1}^{n} b_i \times w_i \Longrightarrow \sum_{i=1}^{n} (a_i - mid \times b_i) \times w_i \geq 0

通过二分法不断调整 mid 的值，直到找到最优解。

Dropping Test

给定 n 个数据，每个数据有 (a, b) 两个值，都为整数并且非负。舍弃掉 k 个数据，希望让剩下数据 \frac{\sum a}{\sum b} 尽量大。如果剩下数据所有 b 的和为 0，认为无意义。结果乘以 100，小数部分四舍五入的整数结果返回。

C++
#include <algorithm>
#include <iostream>
#include <utility>
#include <vector>
using namespace std;

int main() {
  int n, k;
  while (cin >> n >> k) {
    if (n == 0 && k == 0) { break; }
    vector<pair<int, int>> nums(n);
    for (int i = 0; i < n; i++) { cin >> nums[i].first; }
    for (int i = 0; i < n; i++) { cin >> nums[i].second; }

    auto check = [&](double x) {
      vector<double> diffs(n);
      for (int i = 0; i < n; ++i) { diffs[i] = nums[i].first - x * nums[i].second; }
      sort(diffs.rbegin(), diffs.rend());
      double sum = 0;
      for (int i = 0; i < n - k; ++i) { sum += diffs[i]; }
      return sum >= 0;
    };

    double left = 0, right = 1e9 + 1;
    for (int i = 0; i < 64; i++) {  // 进行足够次数的二分
      double mid = (left + right) / 2;
      if (check(mid)) {
        left = mid;
      } else {
        right = mid;
      }
    }
    cout << static_cast<int>(100 * (left + 0.005)) << "\n";  // 四舍五入
  }
  return 0;
}
Average and Median

给定 n 个整数，相邻两个位置的数必须至少选择一个，求最大平均值和最大中位数。

C++
#include <algorithm>
#include <cstdint>
#include <iostream>
#include <vector>
using namespace std;

int main() {
  int n;
  cin >> n;
  vector<int64_t> nums(n);
  for (int i = 0; i < n; ++i) { cin >> nums[i]; }
  // 最大平均值问题
  {
    auto check = [&](double x) {
      vector<double> diffs(n);
      for (int i = 0; i < n; ++i) { diffs[i] = nums[i] - x; }
      // 判定条件, i 或 i + 1 必须至少选择其中一个
      vector<vector<double>> dp(n, vector<double>(2, 0));
      dp[0][0] = 0;         // i 不选
      dp[0][1] = diffs[0];  // i 选
      for (int i = 1; i < n; ++i) {
        dp[i][0] = dp[i - 1][1];                                // i 不选, 则 i-1 必须选
        dp[i][1] = max(dp[i - 1][0], dp[i - 1][1]) + diffs[i];  // i 选, 则 i-1 可选可不选
      }
      return max(dp[n - 1][0], dp[n - 1][1]) >= 0;
    };

    double left = 1, right = 1e9 + 1;
    for (int i = 0; i < 64; ++i) {  // 进行足够次数的二分
      double mid = (left + right) / 2;
      if (check(mid)) {
        left = mid;
      } else {
        right = mid;
      }
    }
    cout << left << "\n";
  }
  // 最大上中位数问题
  {
    auto check = [&](int64_t x) {
      vector<int64_t> diffs(n);
      for (int i = 0; i < n; ++i) { diffs[i] = nums[i] >= x ? 1 : -1; }
      // 判定条件, i 或 i + 1 必须至少选择其中一个
      vector<vector<int64_t>> dp(n, vector<int64_t>(2, 0));
      dp[0][0] = 0;         // i 不选
      dp[0][1] = diffs[0];  // i 选
      for (int i = 1; i < n; ++i) {
        dp[i][0] = dp[i - 1][1];                                // i 不选, 则 i-1 必须选
        dp[i][1] = max(dp[i - 1][0], dp[i - 1][1]) + diffs[i];  // i 选, 则 i-1 可选可不选
      }
      return max(dp[n - 1][0], dp[n - 1][1]) > 0;  // 注意这里是大于0
    };

    int64_t left = 1, right = 1e9 + 1;
    for (int i = 0; i < 64; ++i) {  // 进行足够次数的二分
      int64_t mid = (left + right) / 2;
      if (check(mid)) {
        left = mid;
      } else {
        right = mid;
      }
    }
    cout << left << "\n";
  }
  return 0;
}

Tip

  • 最大平均值：转化为 \sum (a_i - mid) \geq 0，二分 mid。
  • 最大上中位数(1)：通过将元素值根据与中位数的大小关系转化为 1 或 -1，判断哪一侧数量更多。
  1. 下中位数：\le mid 的数至少占一半
    上中位数：\ge mid 的数至少占一半

评论