跳转至

分数规划

前言

分数规划是一种较少单独出现的约束优化问题，思想较为简单，有时也会与动态规划等算法一同考察

定义

在信奥中，我们一般讨论的为 01分数规划 ，其数学表达如下：

给定一组\(a_i\)和\(b_i\)，要求给出一组\(w_i\in \{0,1\}\)使得如下这个分式取得最大\最小值(可能要求\(\sum w_i \le k\))

\[\frac{\sum a_i \times w_i}{\sum b_i \times w_i}\]

亦可表示为如下类型：

股市中有 \(n\) 种股票，每种股票有收益 \(a_i\) 和成本 \(b_i\)。用最多 \(100\) 元买股票，如何使总甜度/总价格的比值最大？

在这一案例中，要求就是 \(\sum b_i \times w_i \le 100\)。

核心思想

由于在比值约束下进行优化操作较为困难，我们不妨考虑将其转化为一般的线性约束优化问题再进行解决。具体来说：

不妨设当前解为 \(\lambda\)。此时，若存在一组可行更优解（即可以迭代得到更优解），不难列出式子：

\[\begin{aligned} & \frac{\sum a_{i} \times w_{i}}{\sum b_{i} \times w_{i}} > \lambda \\ \Longrightarrow & \sum a_{i} \times w_{i} > \sum b_{i} \times w_{i} \times \lambda \\ \Longrightarrow & \sum a_{i} \times w_{i}-\lambda \times \sum b_{i} \times w_{i}>0 \\ \Longrightarrow & \sum w_{i} \times\left(a_{i}- \lambda \times b_{i}\right)>0 \end{aligned}\]

这样我们就将比值约束转化为了线性约束，随后即可通过枚举 \(\lambda\) 并检查是否存在一组 \(w_i\) 满足 \(\sum w_{i} \times \left( a_{i}- \lambda \times b_{i}\right)>0\) 得到答案。

对于一个给定的 \(\lambda\) ，若要判断其是否可行，可以先将 \(\left( a_{i}- \lambda \times b_{i}\right)\) 处理出来，因为我们希望其 $ >0 $ ，所以我们排序先一遍，再从大到小贪心取， 若不能满足则回退。

上下界可以设置为极大值和极小值，也可以设置为最小比率和最大比率。

例题

下面笔者将通过数道例题来进行具体介绍

1.P1570 KC 喝咖啡

这道题就是道裸的分数规划题，要注意的是必须取满 \(m\) 种调料。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

double a[205], b[205];
int n, m;

bool check(double x) {
    double tmp[205], ans = 0;
    for (int i = 0; i < n; i++) tmp[i] = a[i] - x * b[i];
    sort (tmp, tmp + n, greater<double>());
    for (int i = 0; i < m; i++)ans += tmp[i];
    return ans > 0;
}

signed main() {
    cin >> n >> m;
    for (int i = 0; i < n; i++) cin >> a[i];
    for (int i = 0; i < n; i++) cin >> b[i];
    double r = INT_MIN, l = INT_MAX;
    for (int i = 0; i < n; i++) {
        r = max(r, a[i] / b[i]);
        l = min(l, a[i] / b[i]);
    }
    while (r - l > 1e-6){
        double mid = l+(r-l)/2;
        if (check(mid))l = mid;
        else r = mid;
    }
    cout<<fixed<<setprecision(3)<<r;
    return 0;
}

2.咕咕咕