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

搜索的方式进行。假设节点编号为i，左儿子为2*i，右儿子为2*i+1。

首先，建立根节点，将其加入队列中。

节点0：{W=20, V=0, level=0, bound=63}

其中，W表示当前背包剩余容量，V表示当前价值，level表示当前搜索到的层数，bound表示该节点的价值上界。

接下来，对于每个节点，可以分为两种情况进行搜索：

1. 装入该物品

节点0的左儿子为节点1，将其加入队列。

节点1：{W=15, V=11, level=1, bound=63}

节点1的剩余容量为15，价值为11，层数为1，其价值上界为63。由于节点1是节点0的左儿子，因此装入了第一个物品，节点1的W和V分别为节点0的W减去第一个物品的重量，以及节点0的V加上第一个物品的价值。

节点1的左儿子为节点3，将其加入队列。

节点3：{W=5, V=26, level=2, bound=47}

节点3的剩余容量为5，价值为26，层数为2，其价值上界为47。由于装入了第二个物品，节点3的W和V分别为节点1的W减去第二个物品的重量，以及节点1的V加上第二个物品的价值。

节点3没有左儿子，因为装入第三个物品后，剩余容量为负数，因此不符合条件，可以直接剪枝。

节点3的右儿子为节点4，将其加入队列。

节点4：{W=5, V=38, level=2, bound=47}

节点4的剩余容量为5，价值为38，层数为2，其价值上界为47。由于装入了第三个物品，节点4的W和V分别为节点1的W减去前三个物品的重量，以及节点1的V加上前三个物品的价值。

节点4没有左儿子，因为装入第四个物品后，剩余容量为负数，因此不符合条件，可以直接剪枝。

节点4的右儿子为节点5，将其加入队列。

节点5：{W=0, V=50, level=2, bound=47}

节点5的剩余容量为0，价值为50，层数为2，其价值上界为47。由于装入了前四个物品，节点5的W和V分别为节点1的W减去前四个物品的重量，以及节点1的V加上前四个物品的价值。

节点5没有左儿子，因为装入第五个物品后，剩余容量为负数，因此不符合条件，可以直接剪枝。

节点5没有右儿子，因为所有物品都已经装入背包中，不需要再搜索。

2. 不装入该物品

节点0的右儿子为节点2，将其加入队列。

节点2：{W=20, V=0, level=1, bound=52}

节点2的剩余容量为20，价值为0，层数为1，其价值上界为52。由于节点2是节点0的右儿子，因此没有装入第一个物品，节点2的W和V与节点0相同。

节点2的左儿子为节点6，将其加入队列。

节点6：{W=17, V=15, level=2, bound=52}

节点6的剩余容量为17，价值为15，层数为2，其价值上界为52。由于不装入第二个物品，节点6的W和V与节点2相同。

节点6的左儿子为节点7，将其加入队列。

节点7：{W=7, V=30, level=3, bound=47}

节点7的剩余容量为7，价值为30，层数为3，其价值上界为47。由于不装入第三个物品，节点7的W和V与节点6相同。

节点7没有左儿子，因为不装入第四个物品后，剩余容量为负数，因此不符合条件，可以直接剪枝。

节点7没有右儿子，因为所有物品都已经装入背包中，不需要再搜索。

节点6的右儿子为节点8，将其加入队列。

节点8：{W=7, V=42, level=3, bound=47}

节点8的剩余容量为7，价值为42，层数为3，其价值上界为47。由于不装入第四个物品，节点8的W和V与节点6相同。

节点8没有左儿子，因为不装入第五个物品后，剩余容量为负数，因此不符合条件，可以直接剪枝。

节点8没有右儿子，因为所有物品都已经装入背包中，不需要再搜索。

节点2的右儿子为节点9，将其加入队列。

节点9：{W=20, V=12, level=2, bound=42}

节点9的剩余容量为20，价值为12，层数为2，其价值上界为42。由于装入第二个物品，节点9的W和V分别为节点2的W减去第二个物品的重量，以及节点2的V加上第二个物品的价值。

节点9的左儿子为节点11，将其加入队列。

节点11：{W=10, V=30, level=3, bound=34}

节点11的剩余容量为10，价值为30，层数为3，其价值上界为34。由于不装入第三个物品，节点11的W和V与节点9相同。

节点11没有左儿子，因为不装入第四个物品后，剩余容量为负数，因此不符合条件，可以直接剪枝。

节点11没有右儿子，因为所有物品都已经装入背包中，不需要再搜索。

节点9的右儿子为节点10，将其加入队列。

节点10：{W=12, V=27, level=3, bound=34}

节点10的剩余容量为12，价值为27，层数为3，其价值上界为34。由于不装入第三个物品，节点10的W和V与节点9相同。

节点10没有左儿子，因为不装入第四个物品后，剩余容量为负数，因此不符合条件，可以直接剪枝。

节点10没有右儿子，因为所有物品都已经装入背包中，不需要再搜索。

最终，搜索完毕，节点5的V即为最优解，为50。