分数规划是这样一个东西：

给定若干元素，每个元素有两个属性值\(a_i,b_i\)，在满足题目要求的某些限制下选择若干元素并求出\(\frac{\sum a}{\sum b}\)的最大值。

如果没有限制的话，肯定是贪心的选。

假设当前选择了一个解\(x_0\)，却并不是\(\frac{\sum a}{\sum b}\)的最大值，我们有

进而

这时候我们要求的东西变成了\(a-bx_0\)，每个元素的贡献就独立了。最大化它的和，如果大于\(0\)，就说明\(\frac{\sum a}{\sum b}\)的最大值比\(x_0\)还要大，反之亦然。

于是我们就不难想到二分了。控制\(x_0\)的上下界，每次取\(mid\)进行求值并判断。

例题：洛谷P4377 [USACO18OPEN]Talent Show

此题的限制是\(\sum b\)不小于于给定值，以\(b\)的和为下标，每选一个物品后用背包转移即可。复杂度\(O(nW\log na)\)。

#include<bits/stdc++.h>

#define LL long long

#define RG register

#define R RG int

#define G if(++ip==ie)fread(ip=buf,1,SZ,stdin)

using namespace std;

const LL SZ=1<<19,N=1009,INF=0xc0c0c0c0c0c0c0c0;

char buf[SZ],*ie=buf+SZ,*ip=ie-1;

int t[N],w[N];

LL f[N];

inline int in(){

	G;while(*ip<'-')G;

	R x=*ip&15;G;

	while(*ip>'-'){x*=10;x+=*ip&15;G;}

	return x;

}

inline void chkmx(RG LL&x,RG LL y){

	if(x<y)x=y;

}

int main(){

	R n=in(),W=in(),i,j,l=0,r=2500000,m;

	RG LL del;

	for(i=1;i<=n;++i)

		w[i]=in(),t[i]=in()*1000;

	while(l<r){

		m=(l+r+1)>>1;

		memset(f+1,128,W<<3);

		for(i=1;i<=n;++i){

			del=t[i]-(LL)w[i]*m;

			for(j=W;~j;--j)

				if(f[j]!=INF)chkmx(f[min(j+w[i],W)],f[j]+del);

		}

		f[W]>=0?l=m:r=m-1;

	}

	printf("%d\n",l);

	return 0;

}