「USACO 2018 Open (Gold)」Talent Show

#题面

#题目描述

Farmer John 要带着他的 $n$ 头奶牛（编号为 $1 \dots n$）到农业展览会上去参加每年的达牛秀！他的第 $i$ 头奶牛重量为 $w_i$，才艺水平为 $t_i$，两者都是整数。

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

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

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

#输入格式

第一行是两个整数，分别表示牛的个数 $n$ 和总重量限制 $W$。

第 $2$ 到 $n + 1$ 行，每行两个整数，第 $i + 1$ 行的整数表示第 $i$ 头奶牛的重量 $w_i$ 和才艺水平 $t_i$。

#输出格式

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

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

#输入输出样例

样例输入 #1

3 15
20 21
10 11
30 31

样例输出 #1

1066

样例解释 #1

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

#数据范围与提示

对于 $100\%$ 的测试点，保证 $1 \leq n \leq 250$，$1 \leq W \leq 1000$，$1 \leq w_i \leq 10^6$，$1 \leq t_i \leq 10^3$。

#分数规划

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

#定义

给出 $a_i$ 和 $b_i$，求一组 $w_i\in\{0,1\}$，最小化或最大化

$$\frac{\sum_{i = 1}^{n} a_i \times w_i}{\sum_{i = 1}^{n} b_i \times w_i}$$

#求解

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

$$\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}$$

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

#思路

0/1 分数规划。

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

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

#代码

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;
}