Skip to content

「USACO 2018 Open (Gold)」Talent Show

检测到 KaTeX 加载失败,可能会导致文中的数学公式无法正常渲染。

#题面

#题目描述

Farmer John 要带着他的 nn 头奶牛(编号为 1n1 \dots n)到农业展览会上去参加每年的达牛秀!他的第 ii 头奶牛重量为 wiw_i,才艺水平为 tit_i,两者都是整数。

在到达时,Farmer John 就被今年达牛秀的新规则吓到了:

(一)参加比赛的一组奶牛必须总重量至少为 WW(这是为了确保是强大的队伍在比赛,而不仅是强大的某头奶牛);并且
(二)总才艺值与总重量的比值最大的一组获得胜利。

Farmer John 注意到他的所有奶牛的总重量不小于 WW,所以他能够派出符合规则(一)的队伍。帮助他确定这样的队伍中能够达到的最佳的才艺与重量的比值。

#输入格式

第一行是两个整数,分别表示牛的个数 nn 和总重量限制 WW

22n+1n + 1 行,每行两个整数,第 i+1i + 1 行的整数表示第 ii 头奶牛的重量 wiw_i 和才艺水平 tit_i

#输出格式

请求出 Farmer John 用一组总重量最少为 WW 的奶牛最大可能达到的总才艺值与总重量的比值。

如果你的答案是 AA,输出 1000×A1000 \times A 向下取整的值,以使得输出是整数(当问题中的数不是一个整数的时候,向下取整操作在向下舍入到整数的时候去除所有小数部分)。

#输入输出样例

样例输入 #1

3 15
20 21
10 11
30 31

样例输出 #1

1066

样例解释 #1

在这个例子中,总体来看最佳的才艺与重量的比值应该是仅用一头才艺值为 1111、重量为 1010 的奶牛,但是由于我们需要至少 1515 单位的重量,最优解最终为使用这头奶牛加上才艺值为 2121、重量为 2020 的奶牛。这样的话才艺与重量的比值为 11+2110+20=3230=1.0666\frac{11 + 21}{10 + 20} = \frac{32}{30} = 1.0666\dots,乘以 10001000 向下取整之后得到 10661066

#数据范围与提示

对于 100%100\% 的测试点,保证 1n2501 \leq n \leq 2501W10001 \leq W \leq 10001wi1061 \leq w_i \leq 10^61ti1031 \leq t_i \leq 10^3

#分数规划

分数规划可以用来求一个分式的极值。

#定义

给出 aia_ibib_i,求一组 wi{0,1}w_i\in\{0,1\},最小化或最大化

i=1nai×wii=1nbi×wi\frac{\sum_{i = 1}^{n} a_i \times w_i}{\sum_{i = 1}^{n} b_i \times w_i}

#求解

分数规划问题的通用求解方法是二分。以求最大值为例,二分一个答案 mid\mathit{mid},有推导过程:

ai×wibi×wi>midai×wimid×biwi>0wi×(aimid×bi)>0\begin{aligned} & \frac{\sum a_i \times w_i}{\sum b_i \times w_i} > \mathit{mid} \\ \Longrightarrow & \sum a_i \times w_i - \mathit{mid} \times \sum b_i\cdot w_i > 0 \\ \Longrightarrow & \sum w_i \times(a_i - \mathit{mid} \times b_i) > 0 \\ \end{aligned}

这样就只需要求出不等号左边的式子的最大值了。如果最大值比 00 要大,说明 mid\mathit{mid} 是可行的,否则不可行。

#思路

0/1 分数规划。

本题中有一个分母至少为 WW 的限制,因此可以考虑使用 0/1 背包代替原先分数规划中的贪心求解。把 wiw_i 作为第 ii 个物品的重量,timid×wit_i - \mathit{mid} \times w_i 作为第 ii 个物品的价值再转移即可。

可以将 W\geq W 的状态都压缩到 WW 上,节省内存空间,代码更简洁,正确性显然。

#代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <iostream>
#include <algorithm>
#include <cmath>

using std::cin;
using std::cout;
const char endl = '\n';

const int N = 255,
W = 1005;
const double eps = 1e-6;

int n, w, a[N], b[N];
double f[W];

bool check(double x) {
std::fill_n(f + 1, w, -1e9);

for (int i = 1; i <= n; i++) {
for (int j = w; j >= 0; j--) {
int k = std::min(w, j + a[i]);

f[k] = std::max(f[k], f[j] + b[i] - x * a[i]);
}
}

return f[w] >= 0;
}

int main() {
std::ios::sync_with_stdio(false);
cin.tie(nullptr);

cin >> n >> w;

for (int i = 1; i <= n; i++) {
cin >> a[i] >> b[i];
}

double l = 0,
r = 1e6;

while (r - l > eps) {
double mid = (l + r) / 2;

if (check(mid)) {
l = mid;
} else {
r = mid;
}
}

cout << static_cast<int>(std::floor(l * 1000)) << endl;

return 0;
}