算法设计与分析分支限界法装载问题画图

分支限界法是一种用于解决组合优化问题的算法设计方法，特别适用于解决诸如装载问题这样的NP难问题。装载问题通常是指在给定的一组物品和有限的容器容量下，如何将物品装入容器中以最大化或最小化某个目标函数（例如，装入的物品总重量或总价值）。

下面是一个简单的例子，说明如何使用分支限界法解决装载问题，并附上相应的图示。

### 问题描述
假设我们有一个容量为10的容器和一组物品，每个物品有一个重量和价值：
- 物品1：重量2，价值3
- 物品2：重量3，价值5
- 物品3：重量5，价值7
- 物品4：重量7，价值9

目标是最大化装入容器的物品总价值。

### 分支限界法步骤
1. **根节点**：表示初始状态，所有物品都未装入容器。
2. **分支**：在每个节点，尝试装入一个物品，生成新的节点。
3. **限界**：计算每个节点的上界（即可能的最大价值），并剪掉那些上界低于当前最优解的节点。
4. **回溯**：在搜索过程中记录当前最优解，并在必要时回溯。

### 图示

根节点 (总重量=0, 总价值=0)
|
|-- 装入物品1 (总重量=2, 总价值=3)
|   |
|   |-- 装入物品2 (总重量=5, 总价值=8)
|   |   |
|   |   |-- 装入物品3 (总重量=10, 总价值=15) -> 达到容量上限
|   |
|   |-- 装入物品3 (总重量=7, 总价值=10)
|
|-- 不装入物品1 (总重量=0, 总价值=0)
    |
    |-- 装入物品2 (总重量=3, 总价值=5)
    |   |
    |   |-- 装入物品3 (总重量=8, 总价值=12)
    |
    |-- 不装入物品2 (总重量=0, 总价值=0)
        |
        |-- 装入物品3 (总重量=5, 总价值=7)

### 解释
1. **根节点**：所有物品都未装入容器。
2. **装入物品1**：总重量变为2，总价值变为3。
3. **装入物品2**：总重量变为5，总价值变为8。
4. **装入物品3**：总重量变为10，总价值变为15，达到容量上限。
5. **不装入物品2**：总重量保持2，总价值保持3。
6. **装入物品3**：总重量变为7，总价值变为10。
7. **不装入物品1**：总重量保持0，总价值保持0。
8. **装入物品2**：总重量变为3，总价值变为5。
9. **装入物品3**：总重量变为8，总价值变为12。
10. **不装入物品2**：总重量保持0，总价值保持0。
11. **装入物品3**：总重量变为5，总价值变为7。

通过分支限界法，我们可以找到最优解，即装入物品1、物品2和物品3，总价值为15。