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)以满容量和第一个物品为起点确立了整个二叉树搜索空间的根节点状态

相关新闻

P1071 [NOIP 2009 提高组] 潜伏者

P1071 [NOIP 2009 提高组] 潜伏者

记录156 #include<bits/stdc.h> using namespace std;int main() {// 优化IO速度ios::sync_with_stdio(false);cin.tie(0);string s1,s2,s3;cin>>s1>>s2>>s3;// 1. 定义两个 map// decode_map[密文字符] 明文字符map<char,char> decode_map; /…

2026/11/16 5:13:09 阅读更多 →
鸿蒙 ArkTS 实战:Taxi Fare Estimator 从打车费用估算到出行费用应用完整解析

鸿蒙 ArkTS 实战:Taxi Fare Estimator 从打车费用估算到出行费用应用完整解析

鸿蒙 ArkTS 实战&#xff1a;Taxi Fare Estimator 从打车费用估算到出行费用应用完整解析 前言 打车费用估算 是一个典型的鸿蒙 ArkTS 轻量工具页面。它围绕“根据车型、里程和等待时间估算打车费用&#xff0c;支持快车、专车和豪华三种计价模型。”这个明确需求&#xff0c…

2026/11/16 5:13:09 阅读更多 →
TI PRCM时钟源选择:从寄存器配置到系统级时钟管理实战

TI PRCM时钟源选择:从寄存器配置到系统级时钟管理实战

1. 项目概述&#xff1a;从寄存器手册到系统级时钟设计如果你和我一样&#xff0c;常年泡在嵌入式底层开发里&#xff0c;那对TI&#xff08;德州仪器&#xff09;的PRCM模块一定不陌生。手册里那些密密麻麻的寄存器位域描述&#xff0c;像MPU_CLKSRC、VIDEO_PLL_CLKSRC&#x…

2026/11/16 5:13:09 阅读更多 →

最新新闻

Electron桌面应用开发实战:从环境搭建到打包发布全流程

Electron桌面应用开发实战:从环境搭建到打包发布全流程

做前端这些年&#xff0c;我大部分时间都在跟浏览器标签页打交道&#xff0c;直到第一次把桌面应用跑起来&#xff0c;才发现原来自己一直被限制在地址栏和刷新按钮围起来的框框里。Electron这个词&#xff0c;最开始是在某段时间频繁出现在同事的讨论里&#xff0c;一个用HTML…

2026/11/16 8:22:12 阅读更多 →
滑盖智能锁T109深度解析:结构原理、安装调试与故障排查

滑盖智能锁T109深度解析:结构原理、安装调试与故障排查

简介&#xff1a;亚太天能T109滑盖智能锁产品说明书是一份PDF格式的官方技术文档&#xff0c;主要面向智能锁安装人员、终端用户及售后维护者&#xff0c;帮助快速掌握产品安装、配置与常见故障处理。全包仅1个PDF文件&#xff0c;大小4.37MB&#xff0c;内容结构清晰&#xff…

2026/11/16 6:41:34 阅读更多 →
PMSM弱磁控制原理与Simulink建模:高速AGV驱动系统设计指南

PMSM弱磁控制原理与Simulink建模:高速AGV驱动系统设计指南

上个月我在调试一台高速AGV的驱动系统&#xff0c;整车要求空载跑到8m/s&#xff0c;电机转速已经拉到额定点&#xff0c;驱动器的输出电压也顶到了母线电压极限附近。再往上踩速度指令&#xff0c;转速纹丝不动&#xff0c;三相电流反而开始震荡。那会儿我的第一反应就是&…

2026/11/16 8:22:12 阅读更多 →
C++核心知识点:从内存管理到STL的实战指南

C++核心知识点:从内存管理到STL的实战指南

C 这门语言我前前后后折腾了十几年&#xff0c;用它写过嵌入式驱动、做过游戏服务端&#xff0c;也搭过基础组件库。每次看到新人一头扎进"C 核心知识点"这个搜索词&#xff0c;我其实挺感慨的——这门语言的难点从来不是语法多&#xff0c;而是知识点之间的耦合太深…

2026/11/16 8:22:12 阅读更多 →
T109滑盖智能锁怎么装?安装调试与故障排查全攻略

T109滑盖智能锁怎么装?安装调试与故障排查全攻略

简介&#xff1a;亚太天能T109滑盖智能锁产品说明书以PDF格式发布&#xff0c;适合智能锁用户、安装人员与售后维修人员阅读。内容围绕T109系列指纹密码刷卡锁展开&#xff0c;先介绍前面板、后面板、锁体、机械钥匙、电池盒盖等部件名称与功能&#xff0c;再给出完整安装步骤&…

2026/11/16 7:30:18 阅读更多 →
LLM知识降熵:从信息垄断到理解权下放

LLM知识降熵:从信息垄断到理解权下放

你有没有过这种经历&#xff1a;翻开源码注释、论文摘要或者一份专业报告&#xff0c;每个字都认识&#xff0c;连在一起却像天书。想找人聊聊&#xff0c;身边要么没人懂&#xff0c;要么懂的懒得跟你解释。后来我试着把同一段内容丢给一个大语言模型&#xff0c;几秒钟之后&a…

2026/11/16 8:22:12 阅读更多 →

日新闻

周新闻

月新闻