[USACO08NOV] Buying Hay S

题意

有 n 种草料，每种草料有重量和价格，而且每种都可以无限购买。

要求总重量至少达到 h，并且总花费最小。

思路

先看一个适合小数据验证的朴素枚举：

cpp

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#include <bits/stdc++.h>
using namespace std;

const int INF = 1000000000;

int n, h;
int w[20], c[20];
int best;

void dfs(int id, int weight, int cost) {
    if (cost >= best) {
        return;
    }
    if (weight >= h) {
        best = cost;
        return;
    }
    if (id > n) {
        return;
    }

    // 直接枚举第 id 种草买多少包，适合小数据验证。
    int limit = (h - weight + w[id] - 1) / w[id] + 1;
    for (int cnt = 0; cnt <= limit; ++cnt) {
        dfs(id + 1, weight + cnt * w[id], cost + cnt * c[id]);
    }
}

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

    cin >> n >> h;
    for (int i = 1; i <= n; ++i) {
        cin >> w[i] >> c[i];
    }

    best = INF;
    dfs(1, 0, 0);
    cout << best << '\n';
    return 0;
}

正式做法是完全背包。

如果题目要求“恰好达到 h”，那就是很标准的一维完全背包。这里麻烦一点的地方在于：题目要求的是“至少 h”。

处理这个条件的常用技巧是状态压缩：

定义 dp[j] 表示达到重量 j 的最小花费；
但把所有超过 h 的状态都合并到 dp[h]。

于是转移时，若当前重量是 j，再买一包重量为 w 的草料，就去到：

min(h, j + w)

为什么这样可以？

因为一旦重量已经不小于 h，题目就不再关心你到底多买了几磅，只关心花费是否更小。超过 h 的那些状态继续细分没有意义。

又因为每种草料可以无限买，所以内层容量必须正序枚举，这正是完全背包的写法。

DP 公式

设 $dp_j$ 表示达到重量 $j$ 的最小花费，超过 $H$ 的重量统一截断到 $H$ 。初始化：

dp_0=0,\quad dp_j=+\infty\ (j>0)

购买一种重量 $w_i$ 、价格 $c_i$ 的草料时：

dp_{\min(H,j+w_i)}=\min\left(dp_{\min(H,j+w_i)},\ dp_j+c_i\right)

每种草料可以买无限次，按完全背包方式转移，最终答案为：

dp_H

公式解释：买草料可以超过目标重量，但超过多少并不重要，所以都压到 H。每种草料能无限买，转移会反复用同一种草料改善最小花费。

代码

cpp

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#include <bits/stdc++.h>
using namespace std;

const int INF = 1000000000;

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

    int n, h;
    cin >> n >> h;

    vector<int> dp(h + 1, INF);
    dp[0] = 0;

    for (int i = 1; i <= n; ++i) {
        int weight, cost;
        cin >> weight >> cost;
        for (int j = 0; j <= h; ++j) {
            if (dp[j] == INF) {
                continue;
            }
            int next_weight = min(h, j + weight);
            dp[next_weight] = min(dp[next_weight], dp[j] + cost);
        }
    }

    cout << dp[h] << '\n';
    return 0;
}

复杂度

时间复杂度 $O(nh)$ ，空间复杂度 $O(h)$ 。

总结

这题是“至少型”完全背包的入门题。核心记忆点就是：把所有超过目标的状态都压到终点，再按完全背包正序转移。

一图流解析

这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。