我的算法书 - [USACO18OPEN] Talent Show G

题目解析

这道题是 “01分数规划” 的另一个经典应用场景：背包模型。

它和 P1642 的核心区别在于：P1642 是在树上做选择（树形DP），而这道题是在集合里做选择（背包DP）。

我们要把这个问题拆解成我们熟悉的积木。

P1642 这个题目其实比个题目要难,但是难度确是一个普及+

1. 第一步：熟悉的配方 (01分数规划)

题目要求最大化：

\frac{\text{总才艺}}{\text{总重量}} = \frac{\sum t_i}{\sum w_i}

这和上一题一模一样！我们直接套用二分答案的模板：

二分一个答案 $x$ 。
判定是否存在一种选牛的方案，使得 $\frac{\sum t_i}{\sum w_i} \geqslant x$ 。
变形为： $\sum t_i - x \cdot \sum w_i \geqslant 0$ 。
合并同类项： $\sum (t_i - x \cdot w_i) \geqslant 0$ 。

所以，在 check(x) 函数里，每一头牛都有了一个新的权值： $v_i = t_i - x \cdot w_i$

现在问题变成了：

请你选出一组牛，使得它们的总重量 $\ge W$ ，并且新的权值和 $\sum v_i$ 最大。

如果这个最大值 $\ge 0$ ，说明 $x$ 可行。

2. 第二步：这是什么背包？

这个题目就变成了01背包 恰好装满 这个问题, 在加上一个小的陷阱 : DP 状态压缩技巧：我们可以把所有超过 $W$ 的重量，都“压缩”视为 $W$ 。-> 变成黑洞

这就变成了一个 “带压缩机制的 01 背包” 问题。

因为每一头牛的贡献 $v_i$ 可能是负数，我们不能让 $dp$ 数组从 0 开始（那样我们会错误地选择“不选牛”来作为最优解），必须从 $dp[0]=0$ 这个合法状态开始转移，其他的初始为 $-\infty$ 。

我们要从 $N$ 个物品中选，每个物品有重量 $w_i$ 和价值 $v_i$ 。

限制条件是：总重量 $\ge W$ （注意：是至少 $W$ ，不是至多）。

这里有一个陷阱！

题目说 $W \le 1000$ 。
但是每头牛的重量 $w_i$ 可能高达 $10^6$ 。

如果我们直接开 dp 数组，像普通背包那样 dp[j] 表示重量为 j 时的最大价值，那么 j 可能非常大（ $250 \times 10^6$ ），数组根本开不下！

关键观察：

题目只要求总重量 $\ge W$ 。

这意味着，重量 $1000$ 和重量 $1000000$ 对于达成目标来说，效果是一样的，都满足了“至少 $W$ ”这个条件。

DP 状态压缩技巧：

我们可以把所有超过 $W$ 的重量，都“压缩”视为 $W$ 。

dp[j] 表示：总重量恰好为 $j$ 时的最大新权值和。
dp[W] 表示：总重量 $\ge W$ 时的最大新权值和。

这部分的压缩,如何你是第一次接触,可能觉得难受,

只要能超过W,我们就认可,具体的超过了多少,不需要知道精确的值

其实可以这样想, 一旦总重量超过W,就变成了集合最值问题(都满足 >= w这个条件,选个最大的值),

这在算法里有一个专门的概念叫 “状态饱和 (Saturation)” 或者 “截断 (Clamping)”。

只关心< w 这部分,状态是怎么转移的

此中类型的背包,我称为 有条件(最低消耗)的背包问题

“至少型背包” (Knapsack with “at least” constraint)

或者是 “带阈值的背包”

这和普通的 “至多型背包” (Capacity constraint) 正好是一对镜像：

至多 $W$ ：超过 $W$ 是非法的（要扔掉）。

至少 $W$ ：超过 $W$ 是合法且等价的（要截断）。

不能超过W,那么就不需要开那么大的DP

3. 第三步：状态转移方程

这就变成了一个变种的 01背包问题。

状态定义： $dp[j]$ 表示重量为 $j$ (如果 $j=W$ 则表示 $\ge W$ ) 时的最大价值。
初始化：
- $dp[0] = 0$ (选0头牛，重量0，价值0)。
- 其他 $dp[1 \dots W] = -\infty$ (因为我们要取最大值，且 $v_i$ 可能是负数，初始状态必须非法)。
转移：

对于每一头牛 $i$ （重量 $w_i$ ，价值 $v_i$ ）：

我们要倒序遍历背包容量 $j$ （从 $W$ 到 $0$ ）。

当我们要在当前重量 $j$ 的基础上加上这头牛时，新的重量是 $j + w_i$ 。

但是我们的数组下标最大只有 $W$ ，所以如果 $j + w_i > W$ ，我们就把它放入 $dp[W]$ 。

$dp[\min(W, j + w_i)] = \max(dp[\min(W, j + w_i)], \quad dp[j] + v_i)$

Open in Excalidraw

4. 代码结构梳理

这是这道题的核心逻辑框架：

cpp

copy

        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

        // check 函数逻辑
bool check(double x) {
    // 1. 初始化 dp 数组
    // dp[0] = 0, 其他 = -INF
    for(int i = 1; i <= W; i++) dp[i] = -1e18; // 只要足够小就行
    dp[0] = 0;

    // 2. 01背包 DP
    for(int i = 1; i <= n; i++) {
        double val = t[i] - x * w[i]; // 当前牛的新权值
        
        // 倒序枚举
        // 这里的 j 是“当前已有的重量”，加上 w[i] 变成新重量
        for(int j = W; j >= 0; j--) { 
            // 目标重量：如果超过 W，就当作 W
            int target = min(W, j + w[i]); 
            
            // 状态转移
            dp[target] = max(dp[target], dp[j] + val);
        }
    }

    // 3. 判断
    // dp[W] 存的就是重量 >= W 的最大价值
    return dp[W] >= 0;
}

5. 输出的小坑

题目要求输出 $\lfloor 1000 \times A \rfloor$ 。

在 P1642 里我们输出了保留一位小数，这里要输出整数。

由于浮点数可能有精度误差（比如 $1066.0$ 变成了 $1065.999999$ ），向下取整就会出错。

解决办法：

在二分结束后，计算结果时稍微把 $L$ 调大一点点再取整，或者直接输出时不做处理通常也可以（因为二分次数够多），最稳妥的是不使用 floor，而是直接强转 long long，或者：

cpp

copy

        1
2

        cout << (long long)(l * 1000) << endl;

总结

这道题其实就是：

01分数规划 (外层) + 01背包 (内层)。

它的难点仅在于：如何处理“至少为 W”这个条件。

解决办法是：把所有 $\ge W$ 的状态都存到 dp[W] 里。

🧠 核心逻辑图解

你可以这样想象 dp 数组：

dp[0], dp[1], …, dp[W-1], dp[W]

dp[0] ~ dp[W-1]: 这些格子是严格的“恰好装满”。比如 dp[50] 就代表重量严格等于 50。
dp[W]: 这是一个**“无限大的桶”**。所有重量 $\ge W$ 的方案，不管是 $W$ , $W+1$ , 还是 $W+10000$ ，最后都会掉进这个桶里，并在里面取 max。

复杂度分析

时间复杂度: $O(N \cdot W \cdot \log(\text{精度})) \approx 250 \times 1000 \times 60 \approx 1.5 \times 10^7$ 。非常安全（1秒可以跑 $10^8$ ）。
空间复杂度: $O(W)$ ，只需要一维数组。

代码

cpp

copy

        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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96

        /**
 * Author by Rainboy blog: https://rainboylv.com github : https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * date: 2026-01-06 16:06:26
 * Algorithm: 01分数规划 + 01背包 (带状态压缩: 至少装满W)
 * * 核心逻辑：
 * 1. 二分答案 x，判断是否存在一组牛，使得 (总才艺 / 总重量) >= x
 * 2. 变形为：总才艺 - x * 总重量 >= 0
 * 3. 这里的 DP 用于求 max(总才艺 - x * 总重量)，限制是总重量 >= W
 */
#include <bits/stdc++.h>
using namespace std;
typedef  long long ll;
typedef  unsigned long long ull;

const int maxn = 255;
const int maxw = 1005; 
const ll inf = 1e18; // 足够大，防止负数不够小

int n, m, W;
int w[maxn], t[maxn];
// dp[i] 表示：重量“恰好”为 i 时的最大权值
// 特殊定义：dp[W] 表示重量 “>= W” 时的最大权值 (这是压缩点)
double dp[maxw]; 

void init(){
    std::cin >> n >> W;
    for(int i = 1; i <= n; ++i) {
        std::cin >> w[i] >> t[i];
    }
}

// Check函数：判定比值 x 是否可行
bool check(double x){

    // 1. 初始化 DP
    // 因为权值 t[i] - x*w[i] 可能是负数，且我们要取 max
    // 所以必须初始化为负无穷，只有起点 dp[0] 是合法的 0
    for(int i = 1; i <= W; ++i) 
        dp[i] = -inf;
    dp[0] = 0;

    // 2. 01背包开始
    // 外层枚举物品 (牛)
    for(int i = 1; i <= n; i++) {
        // 当前这头牛的新权值 (分数规划转化后的权值)
        double new_v = (double)t[i] - x * w[i];

        // 内层枚举容量 (重量)
        // 【关键】01背包必须倒序！防止同一头牛被选多次
        // j 代表“加入这头牛之前”的重量状态
        for(int j = W; j >= 0; j--) {

            // 【状态压缩核心】
            // 如果 j + w[i] 超过了 W，我们不需要记录具体是 W+100 还是 W+1000
            // 只要达到 W，对于题目条件“至少W”来说就是等价的
            // 所以我们把所有溢出的重量都截断在 W 这个“桶”里
            int target = min(W, j + w[i]);
            
            // 只有从合法的状态 (非-inf) 转移才有意义
            if( dp[j] != -inf) { 
                dp[target] = std::max(dp[target], dp[j] + new_v);
            }
        }
    }

    // 只要最终状态 (重量 >= W) 的最大权值 >= 0，说明这个平均值 x 是可以达到的
    return dp[W] >= 0;
}

signed main () {
    ios::sync_with_stdio(false); cin.tie(0);
    init();

    // 开始二分答案
    // 最小比值 0
    // 最大比值：假设牛重1，才艺1000，最大也就1000
    double l = 0, r = 1000;

    // 循环100次，精度足够覆盖 double 范围
    // 这种写法比 while(r-l > eps) 更稳健
    for(int i = 1; i <= 100; ++i) {
        double mid = (l + r) / 2;
        if( check(mid) )
            l = mid; // 如果可行，说明答案可能更大 (往右找)
        else
            r = mid; // 如果不可行，说明猜大了 (往左找)
    }
    
    // 题目要求输出 1000 * 答案 的向下取整
    // 这里的 l 就是最终求得的最大比值
    cout << (long long)(l * 1000) << "\n";
    
    return 0;
}

目录

题目解析

1. 第一步：熟悉的配方 (01分数规划)

2. 第二步：这是什么背包？

3. 第三步：状态转移方程

4. 代码结构梳理

5. 输出的小坑

总结

🧠 核心逻辑图解

复杂度分析

代码