这道题可以作为最优比率背包问题的模板题了。好像属于01分数规划。

我们这里用二分答案的方法解决。

题目要我们求\(\frac{\sum{t}}{\sum{w}}\)的最大值。

我们设答案为\(ans\)，则\(ans \leq \frac{\sum{t}}{\sum{w}}\)。

化简一下就得到：

\[\sum{t} - ans \times \sum{w} \geq 0\]

注意上面的式子的条件是存在，而不是任意。

显然这个式子越大越难满足，越小越容易满足。所以我们可以二分答案。

现在谈谈如何check：

题目说参加比赛的奶牛总重量必须至少为\(W\)，但是\(w_i \leq 10^6\)，怎么办？

考虑到\(W \leq 1000\)，我们弄个\(W+1\)代替大于等于它的所有情况。

所以用01背包的方式去dp，最终去看看\(dp[m]\)跟\(dp[m + 1]\)有没有一个满足大于等于0的。如果有就成立。

---

由于自己蔡，在输出的时候又出锅啦。

在最后输出的时候，不要去用floor函数，直接强制类型转换为int即可。暴力下取整。

似乎因为用了这个东西而被卡精度。。。

代码：

#include
    
     using std::cin;using std::cout;using std::endl;const int maxn = 250, maxm = 1005;const double eps = 1e-5;int n, m;int weight[maxn], value[maxn];double val[maxn];double dp[maxm];bool check(double ans) {    for(int i = 1; i <= n; i++) val[i] = value[i] - ans * weight[i];    for(int i = 1; i <= m + 1; i++) dp[i] = -1e18;    for(int i = 1; i <= n; i++) {        for(int j = m + 1; j >= 0; j--) {            dp[std::min(m + 1, j + weight[i])] = std::max(dp[std::min(m + 1, j  + weight[i])], dp[j] + val[i]);        }    }    return dp[m] >= eps || dp[m + 1] >= eps;}int main() {    cin >> n >> m;    double left = 0, right = 0, ans = -1;    for(int i = 1; i <= n; i++) {        cin >> weight[i] >> value[i];        right += value[i];    }    while(right - left > eps) {        double mid = (left + right) * 0.5;        if(check(mid)) ans = mid, left = mid + eps;        else right = mid - eps;    }    printf("%d", (int)(ans * 1000));    return 0;}