[USACO08DEC] Hay For Sale S

题意

有一辆容量为 C 的车，现在有 H 捆草可买。

每捆草有一个体积 V[i]
每捆草最多只能买一次
不能只买一部分
总体积不能超过 C

要求在不超过容量 C 的前提下，让买到的草总体积尽量大。

这张表可以把原题直接翻译成背包模型：

原题对象	背包含义
一捆草	一个只能选一次的物品
草捆体积 `V[i]`	物品重量
草捆体积 `V[i]`	物品价值
车的容量 `C`	背包容量

从这里就能看出，本题本质上是“总容量不超过 C 时，最多能装多少体积”。

思路

先看最直接的暴力：

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

// brute.cpp：小数据暴力解，用来帮助理解题意并辅助对拍。

const int MAXH = 5005;

int c, h;
int volume[MAXH];
int choose_hay[MAXH]; // choose_hay[i] = 0/1，表示第 i 捆草不买/买
int answer;

int calc_volume() {
    int total_volume = 0;
    for (int i = 1; i <= h; i++) {
        if (choose_hay[i] == 1) total_volume += volume[i];
    }
    return total_volume;
}

bool check() {
    return calc_volume() <= c;
}

// dfs_choose 只负责生成完整 01 序列。
void dfs_choose(int dep) {
    if (dep == h + 1) {
        if (check()) {
            int value = calc_volume();
            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 >> c >> h;
    for (int i = 1; i <= h; i++) {
        cin >> volume[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 表示不买或买。递归先生成完整选择，叶子节点再检查总体积是否超过 C，并统计最大装载体积。

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

关键观察是：每捆草的体积既限制了它能不能放进车里，又正好等于“放进去之后占到多少体积”。

于是设：

dp[j] 表示总体积不超过 j 时，最多能买到多少体积的草

这张表说明状态定义：

状态	含义
`dp[j]`	总体积不超过 `j` 时，最多能买到多少体积的草

处理一捆体积为 v 的草时：

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

所以转移就是：

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

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

最后输出 dp[C] 即可。

DP 公式

设 $dp_j$ 表示总体积不超过 $j$ 时最多能买到多少体积的草。处理体积为 $v_i$ 的草时：

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

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

dp_C

公式解释：目标是在容量内尽量买更多体积。买当前草捆时，从剩余容量 j-v_i 的最优值转移，并加上当前体积。

代码

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 MAXH = 5005;
const int MAXC = 50005;

int c, h;
int volume[MAXH];
int dp[MAXC]; // dp[j] 表示总体积不超过 j 时，最多能装下多少体积的草捆

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

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

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

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

    read_input();
    solve();

    return 0;
}

复杂度

时间复杂度： $O(HC)$
空间复杂度： $O(C)$

总结

这题和最基础的 0/1 背包完全同型，只是物品价值刚好等于物品体积。

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

一图流解析

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