题目内容
（请给出正确答案）
[单选题]
以下关于回溯法的描述中，哪一项是错误的？（)
A.以深度优先策略搜索解空间树
B.可用约束条件剪去得不到可行解的子树
C.可用目标函数剪去得不到最优解的子树
D.即使在最坏情形下，其性能亦强于蛮力法
提问人：网友xhh_0168
发布时间：2022-01-07
如搜索结果不匹配，请 
所代表的结点，在该处下一个分量 
的可取值范围是
A、{1，2，3}
B、{1}
C、{1，2}
D、{4}
题目内容
（请给出正确答案）
您可能会需要：
安装简答题APP，拍照搜题省时又省心！
更多“以下关于回溯法的描述中，哪一项是错误的？（)”相关的问题
表示的结点，继续搜索以该结点为根的子树的条件是：
第3题
问题描述:设计一个用回溯法搜索子集空间树的函数,参数包括结点可行性判定函数和上界函数等必要的函数,并将此的数用于解0-1背包问题.
点击查看答案
0-1背包问题描述如下;给定n种物品和一个背包.物品i的重量是wi,其价值为vi背包的容量为C.应如何选择装入背包的物品,使装入背包中物品的总价值最大?
在选择装入肯包的物品时,对每种物品i只有2种选择,即装入背包或不装入背包.不能将物品i装入背包多次,也不能只装入部分的物品i.
0-1背包问题形式化描述如下:给定
,要求n元0-1向量
,
使得
而且
达到最大.
算法设计:对于给定的n种物品的重量和价值,以及背包的容量,计算可装入背包的最大价值.
数据输入:由文件input.txt给出输入数据.第1行有2个正整数n和c,n是物品数,c是背包的容量.接下来的1行中有n个正整数,表示物品的价值.第3行中有n个正整数,表示物品的重量.
结果输出:将计算的装入背包物品的最大价值和最优装入方案输出到文件output.txt
第4题
问题描述:子集和问题的一个实例为.其中,是一个正整数的集合,c是一个正整数.子集和问题判定是否
问题描述:子集和问题的一个实例为
.其中,
是一个正整数的集合,c是一个正整数.子集和问题判定是否存在S的一个子集S1,使得
.试设计一个解子集和问题的回溯法.
点击查看答案
.其中,是一个正整数的集合,c是一个正整数.子集和问题判定是否存在S的一个子集S1,使得.试设计一个解子集和问题的回溯法.算法设计:对于给定的正整数的集合
和正整数c,计算S的一个了集S1,使得
数据输入:由文件input.txt提供输入数据.文件第1行有2个正整数n和c,n表示S的大小,c是子集和的目标值.接下来的1行中,有n个正整数,表示集合S中的元素.
结果输出:将子集和问题的解输出到文件output.txt.当问题无解时,输出“NoSolution!".
第5题
问题描述:最小长度电路板排列问题是大规模电子系统设计中提出的实际问题.该问题的提法是,将n块电路板以最佳排列方案插入带有n个插槽的机箱中.n块电路板的不同的排列方式对应于不同的电路板插入方案.
点击查看答案
设B={1,2,...,n}是n块电路板的集合.集合L={N1,N2,...,Nm}是n块电路板的m个连接块.其中每个连接块N是B的一个子集,且N中的电路板用同一根导线连接在一起.在最小长度电路板排列问题中,连接块的长度是指该连接块中第1块电路板到最后1块电路板之间的距离.例如,设n=8,m=5,给定n块电路板及其m个连接块如下:
这8块电路板的一个可能的排列如图5-1所示.
在最小长度电路板排列问题中,连接块的长度是指该连接块中第1块电路板到最后1块电路板之间的距离.例如,在图5-1所示的电路板排列中,连接块N4的第1块电路板在插槽3中.它的最后1块电路板在插槽6中,因此N4的长度为3.同理N2的长度为2.图5-1中的连接块最大长度为3.
试设计一个回溯法找出所给n块电路板的最佳排列,使得m个连接块中的最大长度达到最小.
算法设计:对于给定的电路板连接块,设计一个算法,找出所给n个电路板的最佳排列,使得m个连接块中最大长度达到最小.
数据输入:由文件input.txt给出输入数据.第1行有2个正整数n和m(1≤m,n≤20).接下来的n行中,每行有m个数.第k行的第j个数为0表示电路板k不在连接块j中,为1表示电路板k在连接块j中.
结果输出:将计算的电路板排列最小长度及其最佳排列输出到文件output.txt.文件的第一行是最小长度:接下来的1行是最佳排列.
第7题
快速排序算法在排序过程中，在待排序数组中确定一个元素为基准元素，根据基准元素把待排序数组划分成两个部分，前面一部分元素值小于等于基准元素，而后面一部分元素值大于基准元素。然后再分别对前后两个部分进一步进行划分。根据上述描述，快速排序算法采用了（）算法设计策略。
A. 分治
B. 动态规划
C. 贪心
D. 回溯
第8题
以下哪一种贪心策略可求得整体最优解？( )
A、以单位重量价值最大策略求解背包问题
B、以重量最轻策略求解背包问题
C、以最近邻点策略求解TSP问题
D、以最早开始时间求解活动安排问题
第10题
设问题规模为n时，某递归算法的时间复杂度记为T(n)，已知T(1)=1, T(n)=2T(n/2)+n/2，用O表示的时间复杂度为( )
A、O(logn)
B、O(n)
C、O(nlogn)
D、O(n2logn)
