[USACO09OCT] Bessie's Weight Problem G

题意

给出 N 捆干草，每捆都有一个重量 S[i]。

每捆干草最多只能吃一次
总重量不能超过上限 H

要求在不超过 H 的前提下，让 Bessie 吃到的总重量尽量大。

这张表把题目直接翻译成了背包模型：

原题对象	背包含义
一捆干草	一个只能选一次的物品
干草重量 `S[i]`	物品重量
干草重量 `S[i]`	物品价值
上限 `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
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#include <bits/stdc++.h>
using namespace std;

// brute.cpp：小数据暴力解，使用 01 序列枚举每捆干草吃或不吃。

const int MAXN = 505;

int h, n;
int weight[MAXN];
int choose_hay[MAXN]; // choose_hay[i] = 0/1，表示第 i 捆干草不吃/吃
int answer;

int calc_weight() {
    int total_weight = 0;
    for (int i = 1; i <= n; i++) {
        if (choose_hay[i] == 1) total_weight += weight[i];
    }
    return total_weight;
}

bool check() {
    return calc_weight() <= h;
}

void dfs_choose(int dep) {
    if (dep == n + 1) {
        if (check()) {
            int value = calc_weight();
            if (answer < value) answer = value;
        }
        return;
    }

    // 第 dep 捆干草的 01 选择：0 不吃，1 吃。
    for (int i = 0; i <= 1; i++) {
        choose_hay[dep] = i;
        dfs_choose(dep + 1);
    }
}

void read_input() {
    cin >> h >> n;
    for (int i = 1; i <= n; i++) {
        cin >> weight[i];
    }
}

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

    read_input();
    dfs_choose(1);
    cout << answer << '\n';

    return 0;
}

brute.cpp 把每捆干草看成一个 01 选择：choose_hay[i] = 0/1 表示不吃或吃。递归先生成完整选择，叶子节点再检查总重量是否超过 H。

这个做法显然正确，但复杂度是 $O(2^N)$ ，只能做小数据验证。

关键观察是：每捆干草的重量既限制了“能不能选”，又正好等于“选了之后获得多少收益”。

所以设：

dp[j] 表示总重量不超过 j 时，最多能吃到多少干草

这张表说明状态定义：

状态	含义
`dp[j]`	总重量不超过 `j` 时，最多能吃到多少干草

处理一捆重量为 w 的干草时：

不吃它：dp[j] 保持原值
吃它：从 dp[j - w] 转移过来，再加上 w

于是转移就是：

dp[j] = max(dp[j], dp[j - w] + w)

因为每捆干草只能吃一次，所以容量必须倒序枚举。

最后输出 dp[H] 即可。

DP 公式

设 $dp_j$ 表示总重量不超过 $j$ 时最多能吃到多少干草。处理重量为 $w_i$ 的干草时：

dp_j=\max(dp_j,\ dp_{j-w_i}+w_i)

其中 $j\geqslant w_i$ ，并且容量倒序枚举。最终答案为：

dp_H

公式解释：每捆干草的重量既是容量消耗，也是收益。状态记录容量内能吃到的最大重量，因此转移形式和 0/1 装箱完全一样。

代码

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

const int MAXN = 505;
const int MAXH = 45005;

int h, n;
int weight[MAXN];
int dp[MAXH]; // dp[j] 表示总重量不超过 j 时，最多能吃到多少干草

void read_input() {
    cin >> h >> n;
    for (int i = 1; i <= n; i++) {
        cin >> weight[i];
    }
}

void solve() {
    for (int i = 1; i <= n; i++) {
        // 每捆干草只能吃一次，所以容量必须倒序枚举。
        for (int j = h; j >= weight[i]; j--) {
            dp[j] = max(dp[j], dp[j - weight[i]] + weight[i]);
        }
    }

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

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

    read_input();
    solve();

    return 0;
}

复杂度

时间复杂度： $O(NH)$
空间复杂度： $O(H)$

总结

这题和普通 0/1 背包几乎完全一样，只是物品价值刚好等于物品重量。

以后看到“每个对象最多选一次，不能超过一个总上限，并且目标是尽量填满”这类条件时，就可以优先往一维 0/1 背包上想。

一图流解析

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