问答题
简述二分检索(折半查找)算法的基本过程。
设输入是一个按非降次序排列的元素表A[i:j]和x,选取A[(i+j)/2]与x比较,如果A[(i+j)/2......
(↓↓↓ 点击下方‘点击查看答案’看完整答案 ↓↓↓)
问答题 用回溯法解布线问题时,求最优解的主要程序段如下:如果布线区域划分为n×m的方格阵列,扩展每个结点需O(1)的时间,L为最短布线路径的长度,则算法共耗时(O(mn)),构造相应的最短距离需要(O(L))时间。
问答题 用回溯法解0/1背包问题时,计算结点的上界的函数如下所示,请在空格中填入合适的内容。
问答题 请写出用回溯法解装载问题的函数。装载问题:有一批共n个集装箱要装上2艘载重量分别为c1和c2的轮船,其中集装箱i的重量为wi。装载问题要求确定是否有一个合理的装载方案可将这n个集装箱装上这2艘轮船。如果有,找出一种装载方案。