百度文库
即贪心选择来达到 。
29.所谓最优子结构性质是指 问题的最优解包含了其子问题的最优解 。 30.回溯法是指 具有限界函数的深度优先生成法 。
31.用回溯法解题的一个显著特征是在搜索过程中动态产生问题的解空间。在任何时刻，算法只保存从根结点到当前扩展结点的路径。如果解空间树中从根结点到叶结点的最长路径的长度为h(n)，则回溯法所需的计算空间通常为 O(h(n)) ）。
32.回溯法的算法框架按照问题的解空间一般分为 子集树 算法框架与 排列树 算法框架。
33.用回溯法解0/1背包问题时，该问题的解空间结构为 子集树 结构。
34.用回溯法解批处理作业调度问题时，该问题的解空间结构为 排列树 结构。 35.旅行售货员问题的解空间树是 排列树 。
三、算法填空
1.背包问题的贪心算法
void Knapsack(int n,float M,float v[],float w[],float x[]) {n]],价值为v[1..n]的 n个物品，装入容量为M的背包 n]
int i; Sort(n,v,w);
for (i=1;i<=n;i++) x[i]=0; float c=M;
for (i=1;i<=n;i++) {if (w[i]>c) break; x[i]=1; c-=w[i]; }
if (i<=n) x[i]=c/w[i];
}
2.最大子段和: 动态规划算法 int MaxSum(int n, int a[]) {
int sum=0, b=0； 心算法求活动安排问题 template
void GreedySelector(int n, Type s[], Type f[], bool A[]) {
A[1]=true; int j=1;
for (int i=2;i<=n;i++) if (s[i]>=f[j])
{ A[i]=true; j=i; }
else A[i]=false; 6
百度文库
}
4.快速排序
template
void QuickSort (Type a[], int p, int r) {
if (p {int q=Partition(a,p,r); QuickSort (a,p,q-1); 回溯法解迷宫问题 迷宫用二维数组存储，用'H'表示墙,'O'表示通道 int x1,y1,success=0; 给定已按升序排好序的n个元素a[0:n-1]，现要在这n个元素中找出一特定元素x，返回其在数组中的位置，如果未找到返回-1。 写出二分搜索的算法，并分析其时间复杂度。 template int BinarySearch(Type a[], const Type& x, int n) {利用分治算法写出合并排序的算法，并分析其时间复杂度 void MergeSort(Type a[], int left, int right) { if (left void Clique::Backtrack(int i) 顺序表存储表示如下： typedef struct {RedType r[MAXSIZE+1]; high]的记录,枢轴记录到位,并返回其所在位置, int pivotkey; [0]=[low]; ey; ey>=pivotkey) --high; [low]=[high]; ey<=pivotkey) ++low; [high]=[low]; high]作快速排序 int pivotloc; if (low QSort(L,low,pivotloc-1); //对低子表递归排序,pivotloc是枢轴位置 QSort(L,pivotloc+1,high); //对高子表递归排序 } } void QuickSort(SqList &L) {//对顺序表L作快速排序 QSort(L,1,; } 7
计算机算法设计与分析习题及答案
