1 问题概述
分数规划是用于求一类分式的极值问题。
给定两个数列 \(a_i,b_i\)，求出一个数列 \(w_i\in \{0,1\}\)，最小（大）化下列式子：
\[\dfrac{\sum\limits_{i=1}^na_i\times w_i}{\sum\limits_{i=1}^nb_i\times w_i} \]再说直白点就是每个物品有 \(a,b\) 两个权值，选出当中一些物品，使 \(\dfrac{\sum a}{\sum b}\) 最小（大）。
2 解法
解决 01 分数规划问题的通法就是二分。下面以最大值距离说明。
我们二分一个答案 \(mid\)，如果要求的分式值可以大于这个 \(mid\) 那么就说明可行，转移二分区间并记录答案。于是我们就可以推出限免式子：
\[\dfrac{\sum a_i\times w_i}{\sum b_i\times w_i}>mid\\ \sum a_i\times w_i-mid\times\sum b_i\times w_i>0\\ \sum w_i\times (a_i-mid\times b_i)>0 \]所以我们只需要求出 \(\sum w_i\times (a_i-mid\times b_i)\) 的最大值，如果比 \(0\) 大就代表可行，否则一定不可行。
下面举一些例子来说明 01 分数规划的题目的特征。
3 实例
3.1 [USACO18OPEN] Talent Show G
首先转化题目模型如下：
求出 \(\dfrac{\sum t_i}{\sum w_i}\) 的最大值，要满足 \(\sum w_i\ge W\)。
发现要求式子就是 01 分数规划的标准形式，现在问题是怎样求 \(\sum (t_i-mid\times w_i)\) 最大值，还需要保证 \(\sum w_i\ge W\)。
仔细思考一下我们不难发现，如果我们构造一个物品，体积为 \(w_i\)，价值为 \((t_i-mid\times w_i)\)，这个问题就转化为了一个相当朴素的 dp —— 01 背包。所以我们直接套在二分中即可。
代码：
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int Maxn = 2e5 + 5;
const int Inf = 2e9;
const int base = 10000;
int n, W;
int w[Maxn], t[Maxn];
int sum = 0, sw = 0;
int dp[255][2505];
bool check(int x) {
memset(dp, 128, sizeof dp);
dp[0][0] = 0;
for(int i = 0; i < n; i++) {
for(int j = 0; j <= W; j++) {
int k = min(W, j + w[i + 1]);
dp[i + 1][k] = max(dp[i + 1][k], dp[i][j] + t[i + 1] - x * w[i + 1]);
dp[i + 1][j] = max(dp[i + 1][j], dp[i][j]);
}
}
return dp[n][W] > 0;
}
int ans = 0;
void bs() {
int l = 0, r = sum, mid;
while(l <= r) {
mid = (l + r) >> 1;
if(check(mid)) {
ans = mid;
l = mid + 1;
}
else {
r = mid - 1;
}
}
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n >> W;
for(int i = 1; i <= n; i++) {
cin >> w[i] >> t[i];
t[i] *= base;
sum += t[i];
sw += w[i];
}
bs();
cout << ans / 10;
return 0;
}
3.2 [HNOI2009] 最小圈
首先转化模型如下：
每一条边上有两个权值 \(w_i,b_i\)，且 \(b_i=1\)。求出一个环使得 \(\dfrac{\sum w_i}{\sum b_i}\) 最小。
显然这又是一个 01 分数规划问题，我们最后转化出的式子应该是 \(\sum(w_i-mid\times b_i)<0\)，也就是 \(\sum(w_i-mid)<0\)。
我们将边权赋为 \((w_i-mid)\)，然后就是要求一个环使得边权和为负。直接利用 SPFA 判负环即可。
代码如下：
#include <bits/stdc++.h>
using namespace std;
const int Maxn = 2e5 + 5;
const int Inf = 2e9;
int n, m;
struct Edge {
int u, v;
double w;
}ed[Maxn];
int head[Maxn], edgenum;
struct node {
int nxt, to;
double w;
}edge[Maxn];
void add(int u, int v, double w) {
edge[++edgenum] = {head[u], v, w};
head[u] = edgenum;
}
double dis[Maxn];
bool vis[Maxn];
bool SPFA(int x) {
vis[x] = 1;
for(int i = head[x]; i; i = edge[i].nxt) {
int to = edge[i].to;
double w = edge[i].w;
if(dis[x] + w < dis[to]) {
dis[to] = dis[x] + w;
if(vis[to] || SPFA(to)) {
return 1;
}
}
}
vis[x] = 0;
return 0;
}
int check(double x) {
edgenum = 0;
for(int i = 1; i <= n; i++) {
head[i] = 0;
}
for(int i = 1; i <= m; i++) {
add(ed[i].u, ed[i].v, ed[i].w - x);
}
for(int i = 1; i <= n; i++) {
dis[i] = 0;
vis[i] = 0;
}
for(int i = 1; i <= n; i++) {
if(SPFA(i)) {
return 1;
}
}
return 0;
}
double bs() {
double l = -1e7, r = 1e7, mid;
while(r - l >= 1e-9) {
mid = (l + r) / 2.0;
if(check(mid)) {
r = mid;
}
else {
l = mid;
}
}
return l;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n >> m;
for(int i = 1; i <= m; i++) {
cin >> ed[i].u >> ed[i].v >> ed[i].w;
add(ed[i].u, ed[i].v, ed[i].w);
}
double res = bs();
cout << fixed << setprecision(8) << res ;
return 0;
}
通过上述实例不难发现，当题目中出现两个数列和之比，也就是形如 \(\dfrac{\sum a_i}{\sum b_i}\) 的时候，我们往往考虑 01 分数规划。当我们通过二分将问题转化为 \(\sum(a_i-mid\times b_i)\) 的最值与 \(0\) 的关系之后，主要的问题就在于怎样求 \(\sum(a_i-mid\times b_i)\) 的最值了。
标签：分数,01,int,sum,mid,times,Maxn,规划 From： https://www.cnblogs.com/dzbblog/p/18226795