0/1 分数规划

本文介绍分数规划问题及其解法。

引入-项目规划

假设现在你是一家公司的老板，你有三个项目可以选择去做

项目	收益	成本
1	8	4
2	6	3
3	5	4

你想选择 n 项目，使得平均收益率最大化，你该怎么选？

平均收益率概念
平均收益率就是总收益和总成本的比值，可以用式子表示：

平均收益率 = \frac{总收益}{总成本}

首先看到这个问题，我们可以想到贪心，贪心地选择总收益最大总成本最小，但是贪心无法同时兼顾，所以排除。

这时候，我们把问题中的式子转换一下，因为每个项目只有两种情况，选和不选，于是我们可以使用一个 x 数组，x_i 等于 $1$ 表示选这个项目，等于 $0$ 不选。

于是我们的答案就可以变成：

\max \frac{8x_1 + 6x_2 + 5x_3}{4x_1 + 3x_2 + 4x_3} $$ 且 $$ x_i \in [0,1]

如果这时候如果我们想要让平均收益率达到 k ，我们就需要满足

\frac{\sum_{i} a_i \cdot x_i}{\sum_{i} b_i \cdot x_i} \geq k

化简得到

\sum_{i} (a_i - k \cdot b_i) \cdot x_i \geq 0 $$ 所以我们知道，如果想要满足平均收益率达到 $k$，我们就**必须要满足这个式子成立**，我们把它封装起来 $$ f(k) = \sum_{i} (a_i - k \cdot b_i) \cdot x_i

如果 f(k) > 0 那就说明我们可以达到这个答案
如果 f(k) < 0 那就说明我们不能达到这个答案
最后，如果 f(k) =0 那就说说明这个 k 就是我们能达到的最高答案。

如果直接遍历，复杂度会很高，但我们发现，这个判断满足单调性，并且似乎 f(k) 就是二分中的 check 函数，于是可以使用二分来优化。对于 x_i 呢，就对每个项目的权值排序，然后选最大的前 N 个，代码也就随之得出了：

const int N;
const double ex=1e-9;
bool check(double mid,vector<int> a,vector<int> b) {
    int n=a.size();
    priority_queue<double> q;
    for (int i=1;i<=n;i++) {
        double t=a[i]-mid*b[i];
        q.push(t);
    }
    if (q.size()<N) return false;
    double sum=0;
    for (int i=0;i<N;i++) {
        sum+=q.top(); q.pop();
    }
    return sum>ex;
}
double solve(vector<int> a,vector<int> b) {
	int n=a.size();
    
    double l=0,r=0;
    for (int i=1;i<=n;i++) r=max(r,1.0*a[i]/b[i]);

    while (r-l<ex) {
        double mid=(l+r)/2;
        if (check(mid,a,b)) l=mid;
        else r=mid;
    }

    return l;
}

这就是一道标准的分数规划的题目。

基本形式

根据刚刚的例子，我们可以总结出 0/1 分数规划 的基本形式是这样的：

\max \frac{\sum_{i} a_i \cdot x_i}{\sum_{i} b_i \cdot x_i}

因为这个答案是单调递增的，所以可以考虑二分答案，将原式转化为：

f(k) = \sum_{i} (a_i - k \cdot b_i) \cdot x_i

然后运用这个值判断是否能满足要求（也就是把 f 当作 check 函数），就能求解这类问题了

应用

洛谷 P4377 [USACO18OPEN] Talent Show G

题目大意

给你 n 组数字 a_i,b_i ，要求在其中选出 k (1 \leq k \leq n) 组数，求 \max \frac{\sum_{i} a_i \cdot x_i}{\sum_{i} b_i \cdot x_i} ，前提 \sum_{i} a_i \cdot x_i \geq W

思路

很明显，是一道标准的 0/1 分数规划，我们依旧可以运用之前的思路，将原式转换为：

f(k) = \sum_{i} (a_i - k \cdot b_i) \cdot x_i

但是这一次，我们发现新加了一个前提条件，又该如何做呢？

因为我们的每组数（牛）都可以选或不选，根据前面的转移，我们知道如果有一个 v_i （定义如下）

v_i = a_i - x \cdot b_i

并且

能选出一些牛，使得总重量 ≥ W，且总价值（即 𝑣_𝑖之和） ≥ 0。

那么当前这个答案就是可以的。

因为每组数只有选和不选，可以考虑 0/1 背包，定义和转移如下：

dp[w] = \text{在总重量为 } w \text{ 的时候 } \sum_{i} \{v_i = a_i - x \cdot b_i\} \text{ 的最大值}

dp[w] = \max(dp[w], dp[w-b_i] + t_i - x \cdot w_i)

初始化就是 dp[0]=0，其他赋负无穷即可。

最后我们只需要判断是否有 dp[w] 满足 w > W 且 dp[w]>0 就可以了。

当然，外层还是要套一个二分。

代码

/**
 * Problem: Talent Show G
 * File: Talent Show G.cpp
 * Create Date: 2025/10/8/14:30
 * Last Change Date: 2025/10/8 
 * Editor: code-server
 * Powered by 1000ttank
 */
#include <bits/stdc++.h>
using namespace std;
#define int long long
// #define int __int128
#define endl '\n'

const double ex=1e-8;
const int maxn=260;
const int maxt=1e6+10;
struct Node {
    int w,t;
};
int n,w; 
vector<Node> a;
bool check(int k) {
    vector<int> dp(w+1,-1e15); dp[0]=0;
    for (int i=1;i<=n;i++) {
        for (int j=w;j>=0;j--) {
            if (dp[j]!=-1e15) {
                int shld=min(j+a[i].w,w);
                dp[shld]=max(dp[shld],dp[j]+a[i].t-a[i].w*k);
            }
        }
    }
    return dp[w]>=0;
}
void solve() {
    cin >> n >> w;
    a.assign(n+1,{0,0});
    for (int i=1;i<=n;i++) {
        cin >> a[i].w >> a[i].t; a[i].t*=1000;
    }
    /*
    \sigma_{Z[i]}
    ------------- >= mid
    \sigma_{W[i]}

    \sigma_{Z[i]}-\sigma_{W[i]}*mid >= 0
    \sigma_{Z[i]-W[i]*mid} >= 0
    */

    int l=0,r=1000000;
    while (l<=r) {
        int mid=(l+r)/2;
        if (check(mid)) l=mid+1;
        else r=mid-1;
    }
    cout << l-1 << endl;
}
void init() {
    
}
signed main() {
    // #Define CONTEST_MODEL
    #ifdef CONTEST_MODEL
    #ifndef LOCAL 
    freopen("Luogu-P4377.in","r",stdin);
    freopen("Luogu-P4377.out","w",stdout);
    #endif
    #endif

    ios::sync_with_stdio(false); cin.tie(nullptr);
    init();
    int T=1;
    // cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}