OneCoder Avatar
OneCodercoderli.com · 1024 篇博文
⌘ NOIP

NOIP 全国联赛真题

🎨 视觉封面

【NOIP真题】2001 装箱问题 luogu-P1049 | 适用于 GESP六级 / CSP-J 练习

📅 2026-09-29·✍️ OneCoder·计算中...·⏱️ 10 分钟

日常生活中打包行李或装载货箱,我们总希望能把有限的箱子空间填得越满越好。洛谷 P1049 [NOIP2001 普及组]《装箱问题》看似在问“剩余空间最小化”,但本质上却是一个将物品体积等价转化为物品价值的经典 01 背包变种模型。既然目标是让剩余空间 最小,等价于在容量 的限制下,让装入物品的总体积最大化。理解这种“价值即体积()”的问题降维映射,并熟练运用滚动数组逆序推导,是深入掌握背包模型拓展应用不可或缺的一课。

luogu-P1049 [NOIP2001 普及组] 装箱问题

🔗 洛谷原题传送门:luogu-P1049 [NOIP2001 普及组] 装箱问题

题目描述

有一个箱子容量为 ,同时有 个物品,每个物品有一个体积。

现在从 个物品中,任取若干个装入箱内(也可以不取),使箱子的剩余空间最小。输出这个最小值。

输入格式

第一行共一个整数 ,表示箱子容量。

第二行共一个整数 ,表示物品总数。

接下来 行,每行有一个正整数,表示第 个物品的体积。

输出格式

  • 共一行一个整数,表示箱子最小剩余空间。

输入输出样例

样例输入 #1

Code8 行
24
6
8
3
12
7
9
7

样例输出 #1

Code1 行
0

说明/提示

对于 数据,满足 ,。

【题目来源】

NOIP 2001 普及组第四题


题目深度剖析

1. 问题模型的数学抽象与等价转化

初学者在阅读本题时,容易被“使剩余空间最小”所迷惑,试图直接去求剩余空间。实际上,我们可以通过简单的数学关系建立等价映射:

  • 设箱子的初始总容量为 ;
  • 设最终选择装入箱内的物品体积总和为 ;
  • 则箱子的剩余空间为 。

因为初始容量 是一个固定的常数,要使得 取得最小值,当且仅当装入物品的总体积 取得最大值,且 。

因此,原问题“在容量为 的箱子中使剩余空间最小”,完全等价于:

给定背包容量 ,有 个物品,每个物品的体积为 、价值同样为 。在不超过总容量 的约束下,求能装入物品的最大总价值 。最终答案即为 。

通过这一层等价转化,问题直接归约为最纯粹、最基础的 0/1 背包问题。

2. 01背包动态规划模型构建

(1)状态定义

设二维数组 表示:

只考虑前 个物品,在背包容量上限不超过 的情况下,所能装入的最大总体积。 其中 ,。

(2)状态转移方程

对于第 个物品,其体积为 ,我们只有两种选择:

  1. 不选择第 个物品:背包容量不变,此时最大体积继承自前 个物品在容量 下的最优解,即:
  2. 选择第 个物品(前提是当前容量 ):背包需预留出 的空间,由前 个物品在容量 下的最优解转移而来,并加上当前物品的体积 ,即:

综合两种决策,取最大值:

(3)初始条件与目标
  • 初始条件:当没有物品可选()或背包容量为 ()时,能够装入的最大体积均为 ,即 。
  • 最终目标: 即为前 个物品放入容量为 的背包中所能达到的最大体积。最终输出的剩余空间为 。

3. 空间优化:一维滚动数组与逆序遍历的底层本质

在二维转移方程中,我们发现计算 时,仅仅依赖上一阶段 的状态值(即 和 ),完全不需要更早之前的历史状态。

因此,我们可以省去第一维空间,将二维数组压缩为一维数组 :

  • 一维状态定义: 表示容量为 的背包所能容纳的最大体积。
  • 一维状态转移方程:
为什么 01 背包必须逆序遍历?

在一维滚动数组中,内层循环对容量 的遍历顺序至关重要:

  • 若正序遍历( 从 到 ): 当计算到容量 时,较小容量的 在当前这轮循环中已经被更新过了(即已经包含了第 个物品),再次使用它就会导致第 个物品被重复使用多次——这恰恰是完全背包的行为(如我们在 P1616 中所见)。
  • 必须逆序遍历( 从 倒序递减至 ): 倒序遍历能够确保在更新 时,所访问的 仍然保存的是上一轮(尚未考虑第 个物品时)的旧状态。这就从数学上严格保证了每个物品至多只会被选择一次,完美契合 0/1 背包的本质约束!

4. 复杂度分析与时空开销

  • 时间复杂度: 外层循环遍历 个物品,内层循环遍历容量 (步数为 )。因此总时间复杂度为 。 本题数据范围 ,,最大运算次数为 次。在计算机每秒约 次的运算能力下,执行时间小于 秒,远低于题目给定的 1.0 秒时限。
  • 空间复杂度: 使用一维滚动数组后,仅需开辟一个大小为 的整型数组 dp[MAXV]。对于 ,数组仅占用内存约 ,远远低于 的空间上限。

5. 易错点与边界防坑指南

  1. 容量边界与下界控制: 内层循环终止条件必须为 j >= v[i],当容量小于当前物品体积时,物品根本放不进背包,无需也不应进行状态更新。
  2. 全局数组声明与初始置零: 将 dp 数组声明在全局变量区(BSS 段),全局数组会自动清零,且能避免将大数组分配在栈内存(Linux 栈空间通常限制为 8MB)中引发潜在的运行时段错误(RE)。
  3. 最终结果别忘相减: 许多考生在赛场上写完 0/1 背包模板后,习惯性地直接输出了 dp[V],而本题要求的是最小剩余空间,切记最终输出的是 V - dp[V]!

C++ 源码实现

C++50 行
/**
 * 题目: 【GESP/CSP练习】GESP六级 / CSP-J 题解:luogu-P1049 [NOIP2001 普及组] 装箱问题
 * 题号: P1049
 * 归属: GESP六级 / CSP-J
 * 博客: https://www.coderli.com/gesp-6-luogu-p1049-packing-problem/
 * 标准: C++11 (CCF GESP / CSP 官方规范)
 */

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

// 箱子最大容量 V <= 20000,定义在全局静态存储区预留安全裕量
const int MAXV = 20005;

// 一维滚动数组:dp[j] 表示在当前容量限制为 j 的条件下,能够装入物品的最大总体积
int dp[MAXV];

int main() {
    int V, n;
    // 读入箱子总容量 V
    cin >> V;
    // 读入物品总数 n
    cin >> n;

    // 读入每个物品的体积
    vector<int> v(n);
    for (int i = 0; i < n; ++i) {
        cin >> v[i];
    }

    // 0/1 背包核心动态规划过程
    // 外层循环:逐一考察每一个物品
    for (int i = 0; i < n; ++i) {
        // 内层循环:逆序遍历背包容量 j(从最大容量 V 倒序递减至当前物品体积 v[i])
        // 逆序遍历是 0/1 背包的关键:确保每个物品至多被使用一次
        for (int j = V; j >= v[i]; --j) {
            // 状态转移方程:比较不装该物品(dp[j])与装入该物品(dp[j - v[i]] + v[i])的体积
            dp[j] = max(dp[j], dp[j - v[i]] + v[i]);
        }
    }

    // dp[V] 即为在容量为 V 时所能装入物品的最大总体积
    // 题目要求最小剩余空间,因此最终结果为总容量 V 减去装入的最大体积 dp[V]
    cout << V - dp[V] << "\n";

    return 0;
}
看完题解去实战!OneCoder C++ 信奥远征闯关平台 (oi.coderli.com)
💡 OneCoder 资源指引

所有代码开源上传至 GitHub:yummy-code 仓库 · GESP 专题站:GESP WIKI

🤝 技术交流与答疑

欢迎加入:C++ GESP/CSP 考级答疑群(688906745) 与 Java/Python交流群(982860385),点击可直接加群。

📚

猜你想读 · 相关文章推荐

OneCoder

OneCoder

一个中年人的自留地,记录学习 C++、GESP/NOI、Java、Python 与算法架构的心得体会。本站唯一网址:coderli.com

读者讨论与留言

共 0 条讨论
邮箱必填 · 支持 Markdown 格式与直接回复
💬 还没有读者留言,快来成为第一个讨论者吧!