0/1分数规划
一、分数规划
给出若干二元组 $(v_i,c_i)$ ，要求从中选出一些，使得 $\frac{\sum v_i}{\sum c_i}$ 最大（最小）。
二、解法
先考虑最大，最小同理。
1、二分法
假设问题的最优解为 $ans$ ,则有
$$\frac{\sum v_i}{\sum c_i} \le ans$$
移项
$$\sum v_i \le ans \cdot \sum c_i$$
$$\sum v_i-ans \cdot c_i \le 0$$
如此可以将整体的贡献转化为单个物品的贡献 $v_i-ans \cdot c_i$
关于计算 $ans$ ，我们可以考虑二分，然后判断可行性。
2、Dinkelbach算法
在二分的时候，我们判断可行性时仅用到 $F(mid)$ 的正负性，然后使 $l$ 右移或 $r$ 左移，而对其本身并没有利用到
因此，在二分时，若 $F(mid)>0$ 则将 $l$ 移动到 $F(mid)$ 对应直线的横截距上
$Dinkelbach$ 算法 实质上是一种迭代算法，基于这样的思想：不去二分答案，而是先随便给定一个答案，然后根据更优的解不断移动答案，逼近最优解。理论上它比二分快些
但由于 $Dinkelbach$ 算法 需要保存解，且二分的函数不一定平滑，实际速度不一定比二分快
三、应用
1.分数规划+背包=最优比率背包
应题目条件，在dp时把所有总质量大于等于W的更新全算在f[W]上即可
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=250+1;
const int M=1000+1;
const double eps=1e-6;
int n,m;
int w[N],t[N];
double f[M];
template <typename T>
inline T Min(T a,T b){
return a<b?a:b;
}
template <typename T>
inline T Max(T a,T b){
return a>b?a:b;
}
inline bool check(double x){
fill(f+1,f+m+1,-1e6);
for(int i=1;i<=n;i++)
for(int j=m;j>=0;j--){
int k=Min(m,j+w[i]);
f[k]=Max(f[k],f[j]+t[i]-w[i]*x);
}
return f[m]>=0;
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%d%d",&w[i],&t[i]);
double l=0,r=1e3,mid;
for(;r-l>eps;){
mid=(l+r)/2;
if(check(mid))
l=mid;
else r=mid;
}
printf("%d",int(l*1000));
return 0;
}2.分数规划+最小生成树=最优比率生成树
$$ans \le \frac{F-\sum c_i}{\sum t_i}$$
$$\sum ans \cdot t_i+c_i \le F$$
二分时给边上新附一个权值 $mid \cdot c_i+t_i$ ，按该权值求最小生成树再将结果与 $F$ 比较判断可行性
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=400+1;
const int M=10000+1;
const double eps=1e-6;
int n,m,f,u,v,c,t;
struct edge{
int u,v,c,t;
double w;
inline bool operator < (const edge& x) const{
return w<x.w;
}
} e[M];
int fa[N];
inline int find(int x){
return fa[x]==x?x:fa[x]=find(fa[x]);
}
inline bool check(double x){
for(int i=1;i<=n;i++)
fa[i]=i;
for(int i=1;i<=m;i++)
e[i].w=e[i].c+x*e[i].t;
sort(e+1,e+m+1);
int cnt=0;
double sum=0;
for(int i=1;i<=m;i++){
if(cnt==n-1)
break;
int fu=find(e[i].u),fv=find(e[i].v);
if(fu==fv)
continue;
fa[fv]=fu;
cnt++;
sum+=e[i].w;
}
return sum<=f;
}
int main(){
scanf("%d%d%d",&n,&m,&f);
for(int i=1;i<=m;i++)
scanf("%d%d%d%d",&e[i].u,&e[i].v,&e[i].c,&e[i].t);
double l=0,r=1e9,mid;
for(;r-l>eps;){
mid=(l+r)/2;
if(check(mid))
l=mid;
else r=mid;
}
printf("%.4lf",l);
return 0;
}3.分数规划+负环=最优比率环
二分时判定图上是否有一个环 $R$ 满足
$$mid \le \frac{\sum_i^{i \in V} F_i}{\sum_j^{j \in E} T_j}$$
其中 $V$ 为 $R$ 的点集，$E$ 为 $R$ 的边集
考虑将出点的点权减到边权上
$$\sum mid*T_i-F_i \le 0$$
此时可直接在图上判负环
#include<iostream>
#include<cstdio>
using namespace std;
const int N=1000+1;
const int M=5000+1;
const double eps=1e-6;
int n,m,u,v,t;
int f[N];
int cnt;
int head[N];
double dis[N];
bool vis[N];
struct edge{
int nxt,to,t;
double w;
} e[M];
inline void add(int u,int v,int t){
e[++cnt]=(edge){head[u],v,t};
head[u]=cnt;
}
bool spfa(int u){
vis[u]=1;
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].to;
if(dis[v]>dis[u]+e[i].w){
dis[v]=dis[u]+e[i].w;
if(vis[v] || spfa(v)){
vis[v]=0;
return 1;
}
}
}
vis[u]=0;
return 0;
}
inline bool check(double x){
for(int i=1;i<=m;i++)
e[i].w=x*e[i].t-f[e[i].to];
for(int i=1;i<=n;i++)
if(spfa(i))
return 1;
return 0;
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%d",&f[i]);
for(int i=1;i<=m;i++){
scanf("%d%d%d",&u,&v,&t);
add(u,v,t);
}
double l=0,r=1e6,mid;
for(;r-l>eps;){
mid=(l+r)/2;
if(check(mid))
l=mid;
else r=mid;
}
printf("%.2lf",l);
return 0;
}