21. (计算题) 给定n=4的0-1背包问题：背包容量为C=10，各物品的相关信息如下表所示。 物品 容量(w) 价值(v) 价值/容量 1 4 40 10 2 7 42 6 3 5 25 5 4 3 12 4 搜索结点的优先级ub设置如下：把已经选择的物品总价值(v)，加上背包剩余容量(C-w)与剩下可选择的物品的最高“价值/容量”比的乘积，即 要求： (1) 请阐述分支限界法的基本思想； (2) 用优先队列式分支限界法求该问题的最优解； (3) 画出解空间树的搜索过程。

(1) 分支限界法的基本思想是将问题的解空间划分成若干个子集，每个子集都对应着一个节点，然后通过搜索这些节点来求解问题的最优解。在搜索过程中，我们会根据一定的策略，对每个节点进行扩展，得到其所有可能的子节点，然后通过一些剪枝策略来减少搜索的空间和时间复杂度，最终得到最优解。

(2) 用优先队列式分支限界法求解该问题的最优解：

首先将所有物品按照价值/容量比从大到小排序，得到以下排序：

物品2 > 物品1 > 物品3 > 物品4

然后定义一个优先队列Q，将初始节点加入队列中。每次从队列中取出优先级最高的节点进行扩展，直到队列为空或者无法继续扩展为止。在扩展节点的过程中，我们需要根据当前节点已选的物品和剩余容量，计算出该节点的上界ub，然后根据ub值进行剪枝。

具体求解过程如下：

- 初始节点：背包容量为10，已选物品为空，上界ub = 40 + 10 x 6 = 100
- 扩展节点1：选择物品2，剩余容量为3，已选物品为{2}，上界ub = 42 + 3 x 5 = 57
- 扩展节点2：不选择物品2，剩余容量为10，已选物品为{}，上界ub = 0 + 10 x 10 = 100
- 扩展节点3：选择物品2和物品1，剩余容量为3，已选物品为{2, 1}，上界ub = 82
- 扩展节点4：选择物品2和物品3，剩余容量为2，已选物品为{2, 3}，上界ub = 67
- 扩展节点5：选择物品2和物品4，剩余容量为7，已选物品为{2, 4}，上界ub = 58
- 扩展节点6：不选择物品2和物品1，剩余容量为10，已选物品为{}，上界ub = 0 + 10 x 10 = 100

在以上6个扩展节点中，节点3的上界最大，因此选择节点3继续扩展，得到已选物品为{2, 1}，总价值为82，满足题目要求。

(3) 解空间树的搜索过程如下图所示：

其中，节点的标记方式为： (物品编号，当前背包容量，当前已选物品，当前总价值，当前上界)。每个节点的上界均用ub表示。搜索过程中，优先队列按照节点的上界从大到小排序，选择上界最大的节点进行扩展。在扩展节点时，我们需要根据当前节点已选的物品和剩余容量，计算出该节点的上界ub，然后根据ub值进行剪枝。