第16次内容

📚 课前回顾：装载问题与分支限界法

上节课我们深入学习了装载问题（Loading Problem），这是一个经典的组合优化问题，其本质等价于0-1 背包问题：

给定若干集装箱的重量和一艘船的载重上限，如何选择集装箱使得总装载重量最大，但不超过船的容量？

我们重点探讨了使用 带剪枝优化的宽度优先搜索（BFS） 来求解该问题，其核心思想包括：

1. 状态建模

   • 每个搜索状态表示为 (level, current_weight)，其中 level 是当前处理到第几个集装箱，current_weight 是当前已装载的总重量。
   • 从根节点 (0, 0) 开始，逐层构建决策树（装 / 不装）。

2. 算法实现细节

   • 使用队列（如 queue.Queue 或更高效的 collections.deque）进行 BFS。
   • 在“装入”操作时更新全局最优解 max_weight。
   • 注意边界情况：空列表、容量为 0、所有物品超重等。

3. 算法局限与拓展思考

   • BFS 在最坏情况下需遍历 $2^n$ 个状态，仅适用于小规模问题（如 $n \leq 20$）。
   • 对比动态规划（DP）：DP 时间复杂度为 $O(n \times \text{capacity})$，适合容量较小的场景。
   • 引申出分支限界法、A* 搜索、启发式剪枝等高级策略。

---

本次内容

加上界与最优优先搜索，利用了堆的优先级队列。

1.装载问题