P1049 [NOIP 2001 普及组] 装箱问题

记录157

#include<bits/stdc++.h> using namespace std; int n,v,a[35]; int min_remain=2e4+10;// 记录最小剩余空间，初始化为一个比V大的数 void dfs(int remain_v,int num){// remain_v: 当前剩余体积, num: 当前考虑到了第几个物品 if(num>n){ // 1. 终止条件：所有物品都考虑完了 min_remain=min(min_remain,remain_v); return; } //剪枝：如果当前剩余空间已经比历史最优解还大，没必要继续了（可选优化） // if(remain_v >= min_remain) return; //其实选择当前节点就是一个缩小的过程，剪枝没用到 dfs(remain_v,num+1); if(remain_v>=a[num]){ dfs(remain_v-a[num],num+1); } } int main(){ ios::sync_with_stdio(false); cin.tie(0); cin>>v>>n; for(int i=1;i<=n;i++) cin>>a[i]; dfs(v,1); cout<<min_remain; return 0; }

题目传送门https://www.luogu.com.cn/problem/P1049

前言

我是一名专注信奥赛（CSP-J/S、NOIP）的教练。

• 如果你觉得这篇题解对你有帮助，欢迎点击关注我的CSDN账号，我会持续更新高质量算法解析。
• 我深知算法思维的构建远比单纯通过题目更重要，本系列题解不局限于AC代码的堆砌，而是致力于拆解题目背后的逻辑链条与核心知识点
• 备赛路上若遇瓶颈，欢迎随时评论或私信，我将甄选典型疑难问题，通过视频讲解或撰写专项文章的形式，为你提供深度答疑。

核心解题思路

这道题是一道非常经典的搜索（DFS）与回溯问题，也可以看作是 0-1 背包问题的变种。

1. 问题转化（0-1 选择模型）：
   题目要求从 nn 个物品中选取若干个，使得装入箱子的总体积最大，从而让剩余空间最小。对于每一个物品，我们都只有两种选择：装入箱子或者不装入箱子。这构成了一个典型的二叉树搜索空间。

2. 算法设计（深度优先搜索 DFS）：
   我们可以使用深度优先搜索（DFS）来遍历所有可能的组合情况。在搜索过程中，我们维护两个关键状态：当前的剩余体积remain_v和当前正在考虑的物品编号num。

   • 当考虑第num个物品时，首先选择不装入，剩余体积不变，继续搜索下一个物品。
   • 然后判断如果当前剩余体积大于等于该物品的体积，则选择装入，更新剩余体积，继续搜索下一个物品。
   • 当所有物品都考虑完毕（num > n）时，到达叶子节点，此时用当前的剩余体积去更新全局的最小剩余空间。

代码分块详细解释

1. 全局变量定义与初始化

#include<bits/stdc++.h> using namespace std; int n, v, a[35]; int min_remain = 2e4 + 10; // 记录最小剩余空间，初始化为一个比V大的数

• 详细分析：n记录物品总数，v记录箱子的总容量，数组a用来存储每个物品的体积。min_remain是一个全局变量，用来记录在搜索过程中找到的最小剩余空间。由于题目保证 V≤20000，所以将min_remain初始化为2e4+10（即 20010），确保它比任何可能的剩余空间都要大，从而保证第一次更新时一定能成功。

2. 核心逻辑：DFS 搜索与状态转移

void dfs(int remain_v, int num){ // remain_v: 当前剩余体积, num: 当前考虑到了第几个物品 if(num > n){ // 1. 终止条件：所有物品都考虑完了 min_remain = min(min_remain, remain_v); return; } // 选择1：不装当前物品，直接考虑下一个 dfs(remain_v, num + 1); // 选择2：装当前物品（前提是剩余空间足够） if(remain_v >= a[num]){ dfs(remain_v - a[num], num + 1); } }

• 详细分析：这是代码的灵魂所在，完美体现了回溯法“选与不选”的思想。
  • 递归终止条件：当num > n时，说明前 nn 个物品都已经做出了选择，当前分支的搜索已经结束。此时，用min()函数将当前的剩余体积remain_v与全局最优解min_remain进行比较，保留较小的值。
  • 不装入分支：无论当前物品是否能装下，我们都可以选择不装它。因此，保持remain_v不变，直接递归调用dfs(remain_v, num + 1)去处理下一个物品。
  • 装入分支：只有在当前剩余体积remain_v大于等于当前物品体积a[num]的前提下，我们才能选择装入它。装入后，剩余体积减少为remain_v - a[num]，然后递归调用dfs(remain_v - a[num], num + 1)去处理下一个物品。

3. 主函数：数据读入与启动搜索

int main(){ ios::sync_with_stdio(false); cin.tie(0); cin >> v >> n; for(int i = 1; i <= n; i++) cin >> a[i]; dfs(v, 1); cout << min_remain; return 0; }

• 详细分析：主函数负责读取箱子的总容量v和物品数量n，以及所有物品的体积。随后，以初始剩余体积v和起始物品编号1作为参数，调用dfs(v, 1)启动深度优先搜索。搜索结束后，直接输出全局记录的最小剩余空间min_remain即可。

核心逻辑总结表