1. 用途
分数规划常用于求一个分式的极值，就是给出两个序列\(a_i\)和\(b_i\)，使得\(\dfrac{\sum a_i\times w_i}{\sum b_i\times w_i}\)的值最大或最小，其中\(w \in \{0,1\}\)
通常，题目中还会有类似于\(\sum b_i>w\)的限制
2. 解法
通常使用二分，记当前二分的值为mid
\[\begin{aligned}&\because \dfrac{\sum a_i\times w_i}{\sum b_i\times w_i}\ge mid\\&\therefore \sum a_i\times w_i\ge mid\times \sum b_i\times w_i\\&\therefore\sum a_i\times w_i-mid\times \sum b_i\times w_i\ge 0\\&\therefore \sum w_i \times (a_i-mid\times b_i)\end{aligned} \]所以，在每一次check的时候，求出不等式右边的最大值判断即可，而这一部分显然可以用0/1背包完成
3. 例题
P4377 [USACO18OPEN] Talent Show G
按照上述方法二分即可，对于重量的限制可以以重量为下标，求0/1背包判断即可
代码：
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
int n,w,a[255],b[255];
ll f[10005];
bool check(int x)
{
memset(f,128,sizeof(f));
f[0]=0;
ll tmp=f[w];
for(int i=1;i<=n;i++)
{
for(int j=w;j>=0;j--)
{
if(tmp==f[j]) continue;
int k=j+a[i];
k=min(k,w);
f[k]=max(f[k],f[j]+b[i]-1ll*a[i]*x);
}
}
if(f[w]>=0) return 1;
return 0;
}
int main()
{
scanf("%d%d",&n,&w);
for(int i=1;i<=n;i++)
{
scanf("%d%d",&a[i],&b[i]);
b[i]*=1000;
}
int l=0,r=100000;
while(l<r)
{
// printf("%d %d\n",l,r);
int mid=(l+r+1)>>1;
if(check(mid))
{
l=mid;
}
else r=mid-1;
}
printf("%d",l);
return 0;
}