问题描述:试设计一个用回溯法搜索排列空间树的函数.该函数的参数包括结点可行性判定函数和上

A.当解空间树是排列树时， 搜索时，可以将从根结点到当前扩展结点的路径上的数看成是一个子集。

B.剪枝条件:当路径上的数之和＞c时剪枝

C.该算法搜索至排列树的叶子结点（即第n层结点）时， 就找到了一个解。

D.数据预处理，首先必须将n个数按从小到大排序存放于x[1:n]，这样可以提高该算法的搜索效率。

装载问题描述如下:有一批共n个集装箱要装上艘载重量为c的轮船,其中集装箱i的重量为wi.找出一种最优装载方案,将轮船尽可能装满,即在装载体积不受限制的情况下,将尽可能重的集装箱装上轮船.

算法设计:对于给定的n个集装箱的重量和轮船的重量,计算最优装载方案.

数据输入:由文件input.txt给出输入数据.第1行有2个正整数n和c,n是集装箱数,c是轮船的载重量.接下来的1行中有n个正整数,表示集装箱的重量.

结果输出:将计算的最大装载重量输出到文件output.txt.

A.当其解空间树是n叉树时，其显约束条件是任一行只能安排一个皇后，其隐约束条件是任一列和任一（正反）对角线只能安排一个皇后。

B.当其解空间树是排列树时，其显约束条件是任一行或任一列只能安排一个皇后，其隐约束条件是任一（正反）对角线只能安排一个皇后。

C.算法搜索至叶子结点时，就找到一种新的皇后安排方案

D.两种不同解空间树的算法效率比较，排列树的时间耗费比n叉树要高

A.当其解空间树是n叉树时，其显约束条件是任一行只能安排一个皇后，其隐约束条件是任一列和任一（正反）对角线只能安排一个皇后。

B.当其解空间树是排列树时，其显约束条件是任一行或任一列只能安排一个皇后，其隐约束条件是任一（正反）对角线只能安排一个皇后。

C.算法搜索至叶子结点时，就找到一种新的皇后安排方案

D.两种不同解空间树的算法效率比较，排列树的时间耗费比n叉树要高

A.当解空间树是排列树时， 搜索时，可以将从根结点到当前扩展结点的路径上的数看成是一个子集。

B.剪枝条件:当路径上的数之和＞c时剪枝

C.该算法搜索至排列树的叶子结点（即第n层结点）时， 就找到了一个解。

D.数据预处理，将n个数按从小到大排序存放于x[1:n]，可以提高该算法的搜索效率。

A.当解空间树是排列树时， 搜索时，可以将从根结点到当前扩展结点的路径上的数看成是一个子集。

B.剪枝条件:当路径上的数之和＞c时剪枝

C.该算法搜索至排列树的叶子结点（即第n层结点）时， 就找到了一个解。

D.数据预处理，将n个数按从小到大排序存放于x[1:n]，可以提高该算法的搜索效率。

【问题 1】（8 分）

用回溯法求解此 0-1 背包问题，请填充下面伪代码中（1）～（4）处空缺。

回溯法是一种系统的搜索方法。在确定解空间后，回溯法从根结点开始，按照深度优先策略遍历解空间树，搜索满足约束条件的解。对每一个当前结点，若扩展该结点已经不满足约束条件，则不再继续扩展。为了进一步提高算法的搜索效率，往往需要设计一个限界函数，判断并剪枝那些即使扩展了也不能得到最优解的结点。现在假设已经设计了BOUND(v,w,k,W )函数，其中 v、w、k 和 W分别表示当前已经获得的价值、当前背包的重量、已经确定是否选择的物品数和背包的总容量。对应于搜索树中的某个结点，该函数值表示确定了部分物品是否选择之后，对剩下的物品在满足约束条件的前提下进行选择可能获得的最大价值，若该价值小于等于当前已经得到的最优解，则该结点无需再扩展。

下面给出 0-1背包问题的回溯算法伪代码。

函数参数说明如下:

W：背包容量；n：物品个数；w：重量数组；v：价值数组；fw：获得最大价值时背包的重量；fp：背包获得的最大价值；X：问题的最优解。

变量说明如下：

cw：当前的背包重量；cp：当前获得的价值；k：当前考虑的物品编号；Y：当前已获得的部分解。

A.A对，B对

B.A对，B错

C.A错，B对

D.A错、B错