想法
同样是 01分数规划。
思路
先假设一个不够好的答案 \(mid\)，则原答案可表示为
\[\dfrac{\sum t_i}{\sum w_i}(\sum w_i \geq W) \]我们先不看 \(\sum w_i \geq W\) 这个限制条件。如果 \(mid\) 是一个合法的答案，它一定满足：
\[\begin{aligned} \dfrac{\sum t_i}{\sum w_i}&>mid\\ \sum t_i &> mid\times \sum w_i\\ \sum t_i - mid\times \sum w_i &> 0\\ \sum(t_i - mid\times w_i)&>0 \end{aligned} \]于是我们把 \(t_i - mid \times w_i\) 作为每头牛的权重，这时候想办法怎么让选中的奶牛尽可能大，以满足 \(> 0\) 的条件。
一般来说，我们可以贪心地选。但是在这题中，有一个限制条件 \(\sum w_i \ge W\)，贪心失效了，考虑 DP。
将 \(w_i\) 作为重量，\(t_i - mid\times w_i\) 作为价值，进行 01背包，如果背包体积 \(> W\)，就令其等于 \(W\)——将所有 \(> W\) 的情况合并考虑，这样方便，不需要特殊处理 \(> W\) 的情况。
代码
// Problem: P4377 [USACO18OPEN] Talent Show G
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P4377
// Memory Limit: 128 MB
// Time Limit: 1000 ms
// Author: Moyou
// Copyright (c) 2022 Moyou All rights reserved.
// Date: 2022-12-21 16:58:52
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#define INF 0x3f3f3f3f
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
const int N = 260;
const double eps = 1e-4;
int w[N], t[N];
double f[1010];
int n, W;
bool check(double mid)
{
memset(f, -0x3f, sizeof f);
f[0] = 0;
for (int i = 1; i <= n; i++)
{
for (int j = W; j >= 0; j--)
{
int v = min(j + w[i], W);
f[v] = max(f[v], f[j] + (t[i] - (LL)w[i] * mid));
}
}
return f[W] >= 0;
}
int main()
{
cin >> n >> W;
for (int i = 1; i <= n; i++)
cin >> w[i] >> t[i];
double l = 0, r = 1e6;
while (r - l > eps)
{
double mid = (l + r) / 2;
if (check(mid))
l = mid;
else
r = mid;
}
cout << (int)(1000 * l) << endl;
return 0;
}