分数规划出现在了我们今天的模拟赛中，看在这个名字深得我心而且我能看懂证明和内容的份上，给开个专题吧！
\(1.定义\)：
分数规划就是求分数的极值。
形象一点就是，给出\(a_i\)和\(b_i\)，求一组\(w_i \in \{0,1\}\)最小化或者最大化下面的算式：
\(2.解法\)：
最简单的一个方法是二分答案，我们二分一个\(mid\)，假设上述算式 \(>\) \(mid\),也就是：
\[\frac{sum_{i=1}^{n} a_i*w_i}{\sum_{i=1}^{n} b_i*w_i} > mid \]这里的符号可能不是\(>\)而是\(\ge\)，甚至还可能是\(\le\),具体看题目，让你二分什么，答案就是什么，其实就是因题而异。
那么我们给他化个简吧，就是这样：
\[ \sum_{i=1}^{n} a_i*w_i > mid \times \sum_{i=1}^{n} b_i*w_i \\=>\sum_{i=1}^{n} a_i*w_i - mid \times \sum_{i=1}^{n} b_i*w_i > 0 \]显而易见，我们可以提出一个\(\sum_{i=1}^{n} w_i\)，故原式为：
\[\sum_{i=1}^{n} w_i \times(a_i-mid \times b_i) > 0 \]那么只要求出不等号左边的式子的最大值就行了。如果最大值比\(0\)要大，说明 \(mid\) 是可行的，否则不可行。
说了这么多，来补一下题吧23333。
对于这个题，我们简化一下题意：
有\(n\)个物品，每个物品有两个权值\(a\)和\(b\)，你需要确定一组\(w_i \in \{0,1\}\),使得 \(\frac{\sum a_i \times w_i}{\sum b_i \times w_i}\)最大，但是要求\(\sum w_i \times b_i \ge W\)。
本题多了分母至少为\(W\)的限制，因此无法再使用贪心。
可以考虑动态规划，把\(b_i\)作为第\(i\)个物品的重量，\(a_i - mid \times b_i\)作为第\(i\)个物品的价值，然后问题就转化成\(01\)背包，来个代码吧！
double f[1010];
bool check(double mid) {
for (int i = 1; i <= W; i++) f[i] = -1e9;
for (int i = 1; i <= n; i++)
for (int j = W; j >= 0; j--) {
int k = min(W, j + b[i]);
f[k] = max(f[k], f[j] + a[i] - mid * b[i]);
}
return f[W] > 0;
}