[NOIP 2001 普及组] 装箱问题

题意

给出一个容量为 V 的箱子，以及 n 个物品的体积。

每个物品最多只能选一次，要求从中选出若干个放进箱子，使：

总体积不超过 V
箱子的剩余空间尽量小

思路

先看最直接的暴力：

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// brute.cpp：小数据暴力解，使用 01 序列枚举每个物品放或不放。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 35;

int capacity;          // 箱子容量
int n;                 // 物品数量
int a[MAXN];           // 每个物品的体积
int choose_item[MAXN]; // choose_item[i] = 0/1，表示第 i 个物品不放/放
int best_fill;         // 当前能装下的最大总体积

int calc_volume() {
    int sum_volume = 0;
    for (int i = 1; i <= n; i++) {
        if (choose_item[i] == 1) sum_volume += a[i];
    }
    return sum_volume;
}

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

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

    // 第 dep 个物品的 01 选择：0 不放，1 放。
    for (int i = 0; i <= 1; i++) {
        choose_item[dep] = i;
        dfs_choose(dep + 1);
    }
}

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

    cin >> capacity;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    best_fill = 0;
    dfs_choose(1);

    cout << capacity - best_fill << '\n';
    return 0;
}

brute.cpp 把每个物品看成一个 01 选择：choose_item[i] = 0/1 表示不放或放。递归先生成完整选择，叶子节点再检查总体积是否超过容量，并记录最大装入体积。

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

关键观察是：题目虽然问“最小剩余空间”，但完全可以先反过来求：

在不超过 V 的前提下，最多能装下多少体积

如果这个最大装入体积是 best，那么答案就是：

V - best

这样题目就变成了一个最基础的 0/1 背包：

每个物品只能选一次
容量是箱子体积 V
物品体积既是“重量”，也是“收益”

设：

dp[j] 表示容量不超过 j 时，最多能装下多少体积

加入一个体积为 a[i] 的物品时：

不放它：状态不变
放它：从 dp[j - a[i]] 转移，再加上 a[i]

于是转移是：

dp[j] = max(dp[j], dp[j - a[i]] + a[i])

由于每个物品只能用一次，容量维必须倒序枚举。

状态表

这张表说明状态的含义：

状态	含义
`dp[j]`	容量不超过 `j` 时，最多能装下多少体积

从这个定义可以看出，DP 只关心“在给定容量下最多装多少”，不需要记录具体选了哪些物品。因此一维状态就足够。

最后输出 V - dp[V] 即可。

DP 公式

设 $dp_j$ 表示容量不超过 $j$ 时最多能装下多少体积。处理体积为 $a_i$ 的物品时：

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

其中 $j\geqslant a_i$ ，并且容量倒序枚举。设最大装入体积为 $dp_V$ ，最终剩余空间为：

V-dp_V

公式解释：这题等价于在不超过箱子体积的前提下尽量多装。dp_j 记录容量 j 内能装的最大体积，最后用总容量减去最大装入体积就是剩余空间。

样例 DP 表格

以样例为例： $V = 24, n = 6$ ，物品体积为 $8, 3, 12, 7, 9, 7$ 。

处理物品	体积 $a_i$	$dp$ 变化（关键容量）
初始	—	$dp_{0 \sim 24} = 0$
物品 1	8	$dp_{8 \sim 24} = 8$
物品 2	3	$dp_{3 \sim 7} = 3, dp_{8 \sim 10} = 8, dp_{11 \sim 24} = 11$
物品 3	12	$dp_{12 \sim 14} = 12, dp_{15 \sim 22} = 15, dp_{23 \sim 24} = 23$
物品 4	7	$dp_{7} = 7, dp_{10} = 10, dp_{18 \sim 24} = 18 \sim 24$ （ $dp_{24} = 24$ 已可达： $8+3+12+1$ ? 不， $8+9+7=24$ ）
物品 5	9	更新后 $dp_{24} = 24$ （ $8+9+7=24$ ）
物品 6	7	$dp_{24}$ 仍为 24

答案 $V - dp_{24} = 24 - 24 = 0$ ，对应选物品 $8, 9, 7$ （总体积恰好 $24$ ）。

代码

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

const int MAXN = 35;
const int MAXV = 20005;

int capacity;          // 箱子容量
int n;                 // 物品数量
int a[MAXN];           // 每个物品的体积
int dp[MAXV];          // dp[j] = 容量不超过 j 时，最多能装下多少体积

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

void solve() {
    memset(dp, 0, sizeof(dp));

    for (int i = 1; i <= n; i++) {
        // 倒序枚举容量，保证每个物品最多只用一次。
        for (int j = capacity; j >= a[i]; j--) {
            dp[j] = max(dp[j], dp[j - a[i]] + a[i]);
        }
    }

    cout << capacity - dp[capacity] << '\n';
}

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

    read_input();
    solve();

    return 0;
}

复杂度

时间复杂度： $O(nV)$
空间复杂度： $O(V)$

总结

这题的关键是把“最小剩余空间”转成“最大装入体积”。

看到这种“总量不超过上限，并且希望尽量贴近上限”的题时，可以优先考虑：

先求不超过上限时的最优装入量
再由它反推出剩余量

一图流解析

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