给定6个物品,重量分别为(5,3,2,10,4,2)，价值分别为(11,8,15,18,12,6),背包容量W=20，应用分支限界法求解0/1背包问题，请写出在解空间树上的搜索过程，利用广度优先

首先，将物品按照单位重量的价值从大到小排序。

| 物品 | 重量 | 价值 | 单位重量价值 |
| :---: | :---: | :---: | :---: |
| 4 | 10 | 18 | 1.8 |
| 3 | 2 | 15 | 7.5 |
| 5 | 4 | 12 | 3 |
| 1 | 5 | 11 | 2.2 |
| 2 | 3 | 8 | 2.67 |
| 6 | 2 | 6 | 3 |

接下来，建立解空间树。树的每个节点表示一个状态，包括已经装入背包的物品和剩余未装入背包的物品。树的根节点表示初始状态，即未选择任何物品。树的每个子节点表示在父节点的基础上，选择或不选择一个物品而得到的状态。如果选择了一个物品，则将物品的重量和价值计入当前状态，并且背包容量减少对应的重量；如果不选择一个物品，则状态不变，背包容量仍然是原来的值。

搜索过程如下图所示，其中红色圆圈表示已处理节点，绿色圆圈表示待处理节点。


在搜索过程中，记录每个节点的界限值。对于一个节点，其界限值表示在该节点为根节点的子树中，所能达到的最大价值。界限值可以通过计算一个上界和一个下界得到。

- 上界：将当前节点之后的所有物品按照单位重量价值从大到小的顺序装入背包，直到背包装满或者没有剩余物品为止。此时得到的总价值就是上界，因为背包已经没有空间可以装更多的物品了。
- 下界：将当前节点之后的所有物品按照单位重量价值从大到小的顺序装入背包，直到超过背包容量或者没有剩余物品为止。此时得到的总价值就是下界，因为背包已经无法再装下更多的物品。

使用广度优先搜索的好处是可以确保找到的第一个可行解一定是最优解。在搜索过程中，如果一个节点的界限值小于当前已知的最优解，则可以直接剪枝，不需要继续搜索该节点的子树。如果一个节点的界限值等于当前已知的最优解，则需要继续搜索该节点的子树，因为该节点的子树中可能存在更优的解。