![P1049 [NOIP 2001 普及组] 装箱问题](http://pic.xiahunao.cn/yaotu/P1049 [NOIP 2001 普及组] 装箱问题)
记录157#includebits/stdc.h using namespace std; int n,v,a[35]; int min_remain2e410;// 记录最小剩余空间初始化为一个比V大的数 void dfs(int remain_v,int num){// remain_v: 当前剩余体积, num: 当前考虑到了第几个物品 if(numn){ // 1. 终止条件所有物品都考虑完了 min_remainmin(min_remain,remain_v); return; } //剪枝如果当前剩余空间已经比历史最优解还大没必要继续了可选优化 // if(remain_v min_remain) return; //其实选择当前节点就是一个缩小的过程剪枝没用到 dfs(remain_v,num1); if(remain_va[num]){ dfs(remain_v-a[num],num1); } } int main(){ ios::sync_with_stdio(false); cin.tie(0); cinvn; for(int i1;in;i) cina[i]; dfs(v,1); coutmin_remain; return 0; }题目传送门https://www.luogu.com.cn/problem/P1049前言我是一名专注信奥赛CSP-J/S、NOIP的教练。如果你觉得这篇题解对你有帮助欢迎点击关注我的CSDN账号我会持续更新高质量算法解析。我深知算法思维的构建远比单纯通过题目更重要本系列题解不局限于AC代码的堆砌而是致力于拆解题目背后的逻辑链条与核心知识点备赛路上若遇瓶颈欢迎随时评论或私信我将甄选典型疑难问题通过视频讲解或撰写专项文章的形式为你提供深度答疑。核心解题思路这道题是一道非常经典的搜索DFS与回溯问题也可以看作是 0-1 背包问题的变种。问题转化0-1 选择模型题目要求从 nn 个物品中选取若干个使得装入箱子的总体积最大从而让剩余空间最小。对于每一个物品我们都只有两种选择装入箱子或者不装入箱子。这构成了一个典型的二叉树搜索空间。算法设计深度优先搜索 DFS我们可以使用深度优先搜索DFS来遍历所有可能的组合情况。在搜索过程中我们维护两个关键状态当前的剩余体积remain_v和当前正在考虑的物品编号num。当考虑第num个物品时首先选择不装入剩余体积不变继续搜索下一个物品。然后判断如果当前剩余体积大于等于该物品的体积则选择装入更新剩余体积继续搜索下一个物品。当所有物品都考虑完毕num n时到达叶子节点此时用当前的剩余体积去更新全局的最小剩余空间。代码分块详细解释1. 全局变量定义与初始化#includebits/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初始化为2e410即 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即可。核心逻辑总结表代码模块核心变量/操作精炼作用解决的痛点全局最优记录min_remain min(...)记录搜索过程中的最小剩余空间避免了复杂的返回值传递直接在叶子节点更新全局最优解递归终止条件if(num n)判断是否所有物品都已处理完毕标志着一条完整搜索路径的结束是更新最优解的触发点不选分支dfs(remain_v, num1)跳过当前物品探索后续组合保证了“也可以不取”这一题目条件的正确实现选分支dfs(remain_v-a[num], num1)在容量允许时装入当前物品实现了 0-1 背包的核心状态转移并自动完成了空间约束检查搜索启动dfs(v, 1)以满容量和第一个物品为起点确立了整个二叉树搜索空间的根节点状态
记录157#includebits/stdc.h using namespace std; int n,v,a[35]; int min_remain2e410;// 记录最小剩余空间初始化为一个比V大的数 void dfs(int remain_v,int num){// remain_v: 当前剩余体积, num: 当前考虑到了第几个物品 if(numn){ // 1. 终止条件所有物品都考虑完了 min_remainmin(min_remain,remain_v); return; } //剪枝如果当前剩余空间已经比历史最优解还大没必要继续了可选优化 // if(remain_v min_remain) return; //其实选择当前节点就是一个缩小的过程剪枝没用到 dfs(remain_v,num1); if(remain_va[num]){ dfs(remain_v-a[num],num1); } } int main(){ ios::sync_with_stdio(false); cin.tie(0); cinvn; for(int i1;in;i) cina[i]; dfs(v,1); coutmin_remain; return 0; }题目传送门https://www.luogu.com.cn/problem/P1049前言我是一名专注信奥赛CSP-J/S、NOIP的教练。如果你觉得这篇题解对你有帮助欢迎点击关注我的CSDN账号我会持续更新高质量算法解析。我深知算法思维的构建远比单纯通过题目更重要本系列题解不局限于AC代码的堆砌而是致力于拆解题目背后的逻辑链条与核心知识点备赛路上若遇瓶颈欢迎随时评论或私信我将甄选典型疑难问题通过视频讲解或撰写专项文章的形式为你提供深度答疑。核心解题思路这道题是一道非常经典的搜索DFS与回溯问题也可以看作是 0-1 背包问题的变种。问题转化0-1 选择模型题目要求从 nn 个物品中选取若干个使得装入箱子的总体积最大从而让剩余空间最小。对于每一个物品我们都只有两种选择装入箱子或者不装入箱子。这构成了一个典型的二叉树搜索空间。算法设计深度优先搜索 DFS我们可以使用深度优先搜索DFS来遍历所有可能的组合情况。在搜索过程中我们维护两个关键状态当前的剩余体积remain_v和当前正在考虑的物品编号num。当考虑第num个物品时首先选择不装入剩余体积不变继续搜索下一个物品。然后判断如果当前剩余体积大于等于该物品的体积则选择装入更新剩余体积继续搜索下一个物品。当所有物品都考虑完毕num n时到达叶子节点此时用当前的剩余体积去更新全局的最小剩余空间。代码分块详细解释1. 全局变量定义与初始化#includebits/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初始化为2e410即 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即可。核心逻辑总结表代码模块核心变量/操作精炼作用解决的痛点全局最优记录min_remain min(...)记录搜索过程中的最小剩余空间避免了复杂的返回值传递直接在叶子节点更新全局最优解递归终止条件if(num n)判断是否所有物品都已处理完毕标志着一条完整搜索路径的结束是更新最优解的触发点不选分支dfs(remain_v, num1)跳过当前物品探索后续组合保证了“也可以不取”这一题目条件的正确实现选分支dfs(remain_v-a[num], num1)在容量允许时装入当前物品实现了 0-1 背包的核心状态转移并自动完成了空间约束检查搜索启动dfs(v, 1)以满容量和第一个物品为起点确立了整个二叉树搜索空间的根节点状态
![P1071 [NOIP 2009 提高组] 潜伏者](http://pic.xiahunao.cn/yaotu/P1071 [NOIP 2009 提高组] 潜伏者)
平方复杂度无法被常规优化消除｜TaoToken 统一 Key 通道实测)
