🎒 0/1背包问题 — 分支限界法
0/1 Knapsack Problem · Best-First Branch and Bound
📚 算法原理
分支限界法使用优先队列（最大堆），每次选取上界最大的节点扩展。
限界函数：用分数背包（贪心）计算当前节点的价值上界。若上界 ≤ 当前最优解，则剪枝。
步骤：
- 按价值/重量比降序排列物品
- 根节点入优先队列
- 每次弹出上界最大的节点
- 生成左子节点（放入）和右子节点（不放入）
- 计算上界，剪去无效分支
- 找到完整解时更新最优值
✏️ 物品数据
| 物品名 | 重量 | 价值 | 操作 |
|---|
容量:
示例：
🌳 搜索树可视化
点击"单步执行"或"自动演示"开始...
💻 C++ 实现代码
🗺️ 旅行商问题(TSP) — 分支限界法
Traveling Salesman Problem · Best-First Branch and Bound
📚 算法原理
分支限界法求解TSP：从起点出发，逐步扩展部分路径。使用优先队列（最小堆），每次选取下界最小的节点。
限界函数：利用归约矩阵计算路径下界。对代价矩阵做行列归约，归约常数之和即为下界。
步骤：
- 构建代价矩阵，行列归约得根节点下界
- 根节点入优先队列（最小堆）
- 每次弹出下界最小的节点
- 对每个未访问城市生成子节点
- 更新矩阵（禁止回路），重新归约得下界
- 下界 ≥ 当前最优时剪枝
✏️ 代价矩阵
城市数:
∞ 表示不可达（对角线自动设为∞）
示例：
🌳 搜索树可视化
点击"单步执行"或"自动演示"开始...