我的算法书 - [USACO08NOV] Buying Hay S

题目解析

它是学习 “最小代价凑出至少 W 重量” 的教科书级题目。

1. 题目简述

Farmer John 想购买干草，他需要至少 $H$ 磅干草。

现在有 $N$ 种干草，第 $i$ 种的重量是 $P_i$ ，价格是 $C_i$ 。

问：满足总重量 $\ge H$ 的前提下，最小的花费是多少？

2. 为什么选这道题？

核心目标：这道题是“求最小值”，且限制条件是“至少 $H$ ”。
状态压缩：既然只要达到 $H$ 就行，那么 $H+1, H+100, H+1000$ 磅其实都是“满足条件”的状态。我们可以把所有 $\ge H$ 的状态都压缩进 $dp[H]$ 。
无额外干扰：没有分数规划，没有树形结构，纯粹的 DP。

3. 核心逻辑解析 (01背包 vs 完全背包)

虽然原题是完全背包（干草可以买多份），但我为了配合你的需求，先按 01背包（每种干草只能买一份） 的逻辑来讲，你会发现和你刚才写的代码 完全一致。

状态定义：

$dp[j]$ 表示凑出重量恰好为 $j$ (当 $j=H$ 时表示 $\ge H$ ) 的最小花费。

初始化：

$dp[0] = 0$ (凑0重量花0元)。
$dp[1 \dots H] = \text{INF}$ (求最小值，初始要设为无穷大)。

转移方程 (01背包版 - 倒序)：

C++

// 01背包倒序
for (int j = H; j >= 0; j--) {
    // 技巧：所有超过 H 的重量，都扔进 dp[H] 这个“桶”里
    int target = min(H, j + w[i]); 
    
    // 取最小值 min
    dp[target] = min(dp[target], dp[j] + c[i]);
}

转移方程 (原题完全背包版 - 正序)：

这道 P2918 实际代码只需要把 j 的循环改成正序即可。

4. 代码实现 (针对 P2918 的 AC 代码)

这是 P2918 的代码。注意，为了应对原题“完全背包”的特性，内层循环是正序的。

但请你重点关注 min(H, j + 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

        /**
 * P2918 [USACO08NOV] Buying Hay S
 * 核心考点：背包问题 + 状态压缩 (处理“至少为H”的情况)
 */
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

const int MAXH = 50005;
const int INF = 1e9;

int N, H;
int dp[MAXH]; // dp[j]: 获得至少 j 重量干草的最小花费

int main() {
    cin >> N >> H;

    // 1. 初始化
    // 因为求的是“最小”花费，所以初始化为无穷大
    for (int i = 1; i <= H; i++) dp[i] = INF;
    dp[0] = 0; // 起点

    // 2. 读入并进行 DP
    for (int i = 1; i <= N; i++) {
        int w, c;
        cin >> w >> c; // w:重量, c:价格

        // 3. 背包 DP
        // 注意：原题是完全背包(可以重复买)，所以 j 从 0 开始(正序)
        // 如果题目改成 01 背包(只能买一次)，这里改成 for(int j = H; j >= 0; j--) 即可
        for (int j = 0; j <= H; j++) {
            
            // 【核心技巧】状态压缩
            // 只要重量超过 H，就把它归约为 H
            int target = min(H, j + w);
            
            // 只有当前状态 j 是可达的，才能转移
            if (dp[j] != INF) {
                dp[target] = min(dp[target], dp[j] + c);
            }
        }
    }

    // 4. 输出
    // dp[H] 存的就是“重量 >= H”的最小花费
    cout << dp[H] << endl;

    return 0;
}

5. 总结这个套路

以后只要看到题目要求：

“至少” 获得 $W$ 的重量/体积/分数。
求最小代价（或者在满足至少 $W$ 的情况下求最大收益）。

通解模板就是：

数组开到 $W$ 大小。
转移时目标下标写成 min(W, j + w)。
$dp[W]$ 即为答案。

这道 P2918 是最纯粹的练习题，快去切了它！🔪

代码

[include-code] Error: Failed to read file ./1.cpp.
ENOENT: no such file or directory, open '/home/runner/work/rbook_nunjucks/rbook_nunjucks/problems/luogu/2918/1.cpp'

代码2

另一种风格

这份代码使用了 完全背包 的思路来解决问题，并且使用了一种和我们之前讨论的“状态压缩到 $H$ ”略有不同的策略：“允许越界，最后扫描”。

这两种方法都是正确的。这份代码的做法是：既然要凑够至少 $H$ ，那我就干脆算到 $H + \text{max\_weight}$ 这么多，最后在 $\ge H$ 的范围内找一个最小值。

下面是详细的注释版本:

cpp