01分数规划

给定 $a_1,\cdots,a_n$ 以及 $b_1,\cdots,b_n$，求一组 $x_i$，使得：

• $\sum b_{x_i}\ge W$
• $\dfrac{\sum a_{x_i}}{\sum b_{x_i}}$ 最大

求这个最大值，保留三位小数。

---

显然是 01 分数规划。考虑二分，假设目前二分到 $t$，我们要判断是否有一组 $x_i$，使得 $\dfrac{\sum a_{x_i}}{\sum b_{x_i}}\ge t$。
变形得

$$\sum (a_{x_i}-t\times b_{x_i})\ge 0$$

类似于背包问题的方程。
以 $W$ 为背包大小，$b_i$ 为物品重量，$a_i-t\times b_i$ 为物品价值，跑 01 背包即可，$dp_W$ 即为上式中的 $\sum (a_{x_i}-t\times b_{x_i})$。

#include <bits/stdc++.h>
using namespace std;

#define inf 0x3f3f3f3f3f3f3f3f
#define N 300005
#define int long long

int a[N],b[N];

double w,dp[1005];
int n,W;

bool check(){
//	cout<<w<<endl;
	for(int i=1;i<=W;i++)
		dp[i]=-0x3f3f3f3f;
	for(int i=1;i<=n;i++)
		for(int j=W;j>=0;j--)
			if(j+b[i]>=W)
				dp[W]=max(dp[W],dp[j]+(a[i]-b[i]*w));
			else
				dp[j+b[i]]=max(dp[j+b[i]],dp[j]+(a[i]-b[i]*w));
	return dp[W]>=0;
}

signed main(){
	cin>>n>>W;
	for(int i=1;i<=n;i++)
		cin>>b[i]>>a[i];
	
	double l=0,r=1e7;
	while(r-l>1e-10){
		w=(l+r)/2;
		if(check())l=w;
		else r=w;
	}
	cout<<(int)(1000*w)<<endl;
	
	
	return 0;
}