NOIP 全国联赛真题
🎨 视觉封面【NOIP真题】2001 装箱问题 luogu-P1049 | 适用于 GESP六级 / CSP-J 练习
日常生活中打包行李或装载货箱,我们总希望能把有限的箱子空间填得越满越好。洛谷 P1049 [NOIP2001 普及组]《装箱问题》看似在问“剩余空间最小化”,但本质上却是一个将物品体积等价转化为物品价值的经典 01 背包变种模型。既然目标是让剩余空间 最小,等价于在容量 的限制下,让装入物品的总体积最大化。理解这种“价值即体积()”的问题降维映射,并熟练运用滚动数组逆序推导,是深入掌握背包模型拓展应用不可或缺的一课。
luogu-P1049 [NOIP2001 普及组] 装箱问题
🔗 洛谷原题传送门:luogu-P1049 [NOIP2001 普及组] 装箱问题
题目描述
有一个箱子容量为 ,同时有 个物品,每个物品有一个体积。
现在从 个物品中,任取若干个装入箱内(也可以不取),使箱子的剩余空间最小。输出这个最小值。
输入格式
第一行共一个整数 ,表示箱子容量。
第二行共一个整数 ,表示物品总数。
接下来 行,每行有一个正整数,表示第 个物品的体积。
输出格式
- 共一行一个整数,表示箱子最小剩余空间。
输入输出样例
样例输入 #1
24
6
8
3
12
7
9
7样例输出 #1
0说明/提示
对于 数据,满足 ,。
【题目来源】
NOIP 2001 普及组第四题
题目深度剖析
1. 问题模型的数学抽象与等价转化
初学者在阅读本题时,容易被“使剩余空间最小”所迷惑,试图直接去求剩余空间。实际上,我们可以通过简单的数学关系建立等价映射:
- 设箱子的初始总容量为 ;
- 设最终选择装入箱内的物品体积总和为 ;
- 则箱子的剩余空间为 。
因为初始容量 是一个固定的常数,要使得 取得最小值,当且仅当装入物品的总体积 取得最大值,且 。
因此,原问题“在容量为 的箱子中使剩余空间最小”,完全等价于:
给定背包容量 ,有 个物品,每个物品的体积为 、价值同样为 。在不超过总容量 的约束下,求能装入物品的最大总价值 。最终答案即为 。
通过这一层等价转化,问题直接归约为最纯粹、最基础的 0/1 背包问题。
2. 01背包动态规划模型构建
(1)状态定义
设二维数组 表示:
只考虑前 个物品,在背包容量上限不超过 的情况下,所能装入的最大总体积。 其中 ,。
(2)状态转移方程
对于第 个物品,其体积为 ,我们只有两种选择:
- 不选择第 个物品:背包容量不变,此时最大体积继承自前 个物品在容量 下的最优解,即:
- 选择第 个物品(前提是当前容量 ):背包需预留出 的空间,由前 个物品在容量 下的最优解转移而来,并加上当前物品的体积 ,即:
综合两种决策,取最大值:
(3)初始条件与目标
- 初始条件:当没有物品可选()或背包容量为 ()时,能够装入的最大体积均为 ,即 。
- 最终目标: 即为前 个物品放入容量为 的背包中所能达到的最大体积。最终输出的剩余空间为 。
3. 空间优化:一维滚动数组与逆序遍历的底层本质
在二维转移方程中,我们发现计算 时,仅仅依赖上一阶段 的状态值(即 和 ),完全不需要更早之前的历史状态。
因此,我们可以省去第一维空间,将二维数组压缩为一维数组 :
- 一维状态定义: 表示容量为 的背包所能容纳的最大体积。
- 一维状态转移方程:
为什么 01 背包必须逆序遍历?
在一维滚动数组中,内层循环对容量 的遍历顺序至关重要:
- 若正序遍历( 从 到 ): 当计算到容量 时,较小容量的 在当前这轮循环中已经被更新过了(即已经包含了第 个物品),再次使用它就会导致第 个物品被重复使用多次——这恰恰是完全背包的行为(如我们在 P1616 中所见)。
- 必须逆序遍历( 从 倒序递减至 ): 倒序遍历能够确保在更新 时,所访问的 仍然保存的是上一轮(尚未考虑第 个物品时)的旧状态。这就从数学上严格保证了每个物品至多只会被选择一次,完美契合 0/1 背包的本质约束!
4. 复杂度分析与时空开销
- 时间复杂度: 外层循环遍历 个物品,内层循环遍历容量 (步数为 )。因此总时间复杂度为 。 本题数据范围 ,,最大运算次数为 次。在计算机每秒约 次的运算能力下,执行时间小于 秒,远低于题目给定的 1.0 秒时限。
- 空间复杂度:
使用一维滚动数组后,仅需开辟一个大小为 的整型数组
dp[MAXV]。对于 ,数组仅占用内存约 ,远远低于 的空间上限。
5. 易错点与边界防坑指南
- 容量边界与下界控制:
内层循环终止条件必须为
j >= v[i],当容量小于当前物品体积时,物品根本放不进背包,无需也不应进行状态更新。 - 全局数组声明与初始置零:
将
dp数组声明在全局变量区(BSS 段),全局数组会自动清零,且能避免将大数组分配在栈内存(Linux 栈空间通常限制为 8MB)中引发潜在的运行时段错误(RE)。 - 最终结果别忘相减:
许多考生在赛场上写完 0/1 背包模板后,习惯性地直接输出了
dp[V],而本题要求的是最小剩余空间,切记最终输出的是V - dp[V]!
C++ 源码实现
/**
* 题目: 【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;
}所有代码开源上传至 GitHub:yummy-code 仓库 · GESP 专题站:GESP WIKI
欢迎加入:C++ GESP/CSP 考级答疑群(688906745) 与 Java/Python交流群(982860385),点击可直接加群。
猜你想读 · 相关文章推荐
【NOIP真题】2005 采药 luogu-P1048 | 适用于 GESP六级 / CSP-J 练习
在限定的时间或负重预算下,面对一系列各具耗时与价值且不可分割的物品,如何做出取舍以达成总体收益最大化?洛谷 P1048 [NOIP2005 普及组]《采药》是整个动态规划领域中01 背包模型(0/1 Knapsack Problem)无可争议的“Hello World”...
【NOIP真题】2006 开心的金明 luogu-P1060 | 适用于 GESP六级 / CSP-J 练习
面对手头的固定预算和心仪物品的清单,每一件物品既有本身的价格,又有主观的喜爱重要度,如何在预算硬约束下让“开心程度”达到顶峰?洛谷 P1060 [NOIP2006 普及组]《开心的金明》生动刻画了现实消费中的多属性权衡决策。题目的数学本质依然是 01 背包,但其精妙之处...
【NOIP真题】2004 合唱队形 luogu-P1091 | 适用于 GESP六级 / CSP-J 练习
排练合唱队形时,如何让队列呈现先严格递增、后严格递减的“山峰形(单峰形)”,同时移走尽可能少的同学?洛谷 P1091 [NOIP2004 提高组]《合唱队形》是线性动态规划中双向最长上升子序列(Double LIS)的传世经典。题目要求“移走人数最少”,反向思考即为“保...
OneCoder
一个中年人的自留地,记录学习 C++、GESP/NOI、Java、Python 与算法架构的心得体会。本站唯一网址:coderli.com

