设某一机器由 n 个部件组成，每一种部件都可以从 m 个不同的供应商处购得。设 wij 是从供应商 j 处购得的部件 i 的重量，cij 是相应的价格。试设计算法，给出总价格不超过 d 的最小重量机器设计，输出最小重量，以及每个部件的供应商。 （1）用回溯法设计算法，分别给出解向量、解空间（以n=2, m=3为例画出解空间结构）、约束函数、限界函数，并以代码的形式写出算法描述。 （2）用优先队列式分支限界设计算法，以文字或伪代码的形式描述算法，并给出优先队列中活结点的增加和删除全过程，数据如下： n=3，m=2，d=4； w11=1， w12=2， w21=3， w22=2， w31=1， w32=2； c11=3， c12=1， c21=1， c22=3， c31=1， c32=2。

1. 回溯法设计算法：

解向量：设第 i 个部件从第 j 个供应商购得，则解向量为 x = (x1, x2, ..., xn)，其中 xi 表示第 i 个部件的供应商编号，取值范围为 1~m。

解空间：以 n=2, m=3 为例，解空间结构如下图所示：

               +-----------+           +-----------+           +-----------+
               | x1        |           | x1        |           | x1        |
               |           |           |           |           |           |
               | 1         |           | 2         |           | 3         |
               |           |           |           |           |           |
               +-----------+           +-----------+           +-----------+
                   |                       |                       |
                   |                       |                       |
                   |                       |                       |
               +-----------+           +-----------+           +-----------+
               | x2        |           | x2        |           | x2        |
               |           |           |           |           |           |
               | 1         |           | 2         |           | 3         |
               |           |           |           |           |           |
               +-----------+           +-----------+           +-----------+

约束函数：对于每个部件 i，其选择的供应商 j 必须满足总价格不超过 d 的限制，即：

∑(cij) ≤ d

限界函数：对于已经选择的部件 i，计算其余部件的最小重量，如果已经超过了当前最优解，则剪枝。

算法描述：

1. 初始化：最小重量 min_weight = ∞，当前重量 curr_weight = 0，当前价格 curr_price = 0，解向量 x = (0, 0, ..., 0)，起始部件 i = 1。
2. 如果 i > n，则更新最优解并返回。
3. 对于部件 i，枚举其可选择的供应商 j。
4. 如果 ∑(cij) <= d，则更新当前重量和价格，将 x[i] 设为 j，继续搜索下一个部件 i+1。
5. 否则，剪枝，回溯到上一层，尝试选择该部件的其他供应商。
6. 如果已经搜索完所有的供应商，回溯到上一层。

2. 优先队列式分支限界设计算法：

算法描述：

1. 初始化：最小重量 min_weight = ∞，当前重量 curr_weight = 0，当前价格 curr_price = 0，解向量 x = (0, 0, ..., 0)，起始部件 i = 1。
2. 初始化优先队列，将根结点加入队列。
3. 当队列不为空时，取出队首结点并扩展其子结点。
4. 对于当前扩展的结点，计算其可行解中最小重量 lower_bound。如果 lower_bound >= min_weight，则剪枝，回溯到上一层。
5. 如果当前结点是叶子结点，则更新最优解并回溯到上一层。
6. 否则，将扩展出的子结点加入优先队列，并继续扩展队首结点。
7. 重复步骤3-6，直到找到最优解或队列为空。

优先队列中活结点的增加和删除全过程：

假设当前扩展的结点为 node，其可行解为 x，其子结点为 node1, node2, ..., nodek。

1. 将结点 node 弹出队列。
2. 对于每个子结点 nodei，计算其可行解中最小重量 lower_bound，将其加入优先队列中。
3. 重复步骤1-2，直到队列为空。