【算法设计与分析】期末复习_算法分析期末复习

复习大纲

第一章算法概述

1.1算法与程序

算法：是解决问题的一种方法或一个过程，是由若干条指令组成的有穷序列。
算法性质：
1.输入：有零个或多个
2.输出：至少一个
3.确定性：组成算法的每条指令清晰无歧义
4.有限性：算法中每条指令的执行次数和执行时间是有限的
5.算法与程序的区别：程序是算法用某种程序设计语言的具体实现，可以不满足有限性。

1.2 算法复杂性分析

1.算法的复杂性分时间复杂性和空间复杂性。
2.三种情况下的时间复杂性，可操作性最好最有实际价值的是最坏情况下的时间复杂性。
3.算法复杂性的渐进分析：O，o，Ω，ω，Θ

第二章递归与分治策略

分治法的基本思想

将一个规模为n的问题分解为k个规模较小的子问题，这些子问题互相独立且与原问题相同。递归地解这些子问题，然后将各子问题的解合并得到原问题的解。

递归与分治的关系：

由分治法产生的子问题往往是原问题的较小模式，反复应用分治法，可以使子问题与原问题类型一致且规模不断缩小，最终使子问题缩小到很容易求解，因此用递归求解。

用分治法解决的问题的几个特征：

•问题的规模缩小到一定的程度可以容易地解决；
•问题可以分解为若干个规模较小的相同问题；
•利用原问题分解出的子问题的解可以合并为原问题的解；
•问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。如果子问题不是相互独立的，可以用动态规划法。

例题：

深刻理解算法的设计并能够进行时间复杂度分析
排列问题（包括有重复元素的情况），二分搜索，大整数乘法和矩阵乘法的分治思想，合并排序，快速排序，棋盘覆盖的思想。

第三章动态规划

动态规划的基本思想：

将待求解问题分解成若干个子问题，如果各个子问题不是独立的，不同的子问题的个数只是多项式量级，为避免大量的重复计算，用一个表记录所有已解决的子问题的答案，而在需要的时候再找出已求得的答案。

分治与动态规划算法的异同：

分治法与动态规划法的相同点是:将待求解的问题分解成若干个子问题,先求解子问题,然后从这些子问题的解得到原问题的解。
两者的不同点是:适合于用动态规划法求解的问题,经分解得到的子问题往往不是互相独立的。而用分治法求解的问题,经分解得到的子问题往往是互相独立的。

理解动态规划算法的基本要素：

• 最优子结构性质：问题的最优解包含了其子问题的最优解。
• 重叠子问题性质：有些子问题被反复计算多次。

动态规划算法求解问题的步骤：

• 找出最优解的性质，并刻画其结构特征
• 递归地定义最优值
• 以自底向上的方式计算出最优值
• 构造最优解

例题：

深刻理解矩阵连乘问题、最长公共子序列问题、最大子段和问题和0-1背包问题的动态规划算法，并进行时间复杂度和空间复杂度分析。

第四章贪心算法

理解贪心算法的基本要素：

• 贪心选择性质：所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。
• 最优子结构性质。

贪心算法与动态规划算法的异同点：

（1）共同点：都需要最优子结构性质，都用来求最优化问题。
（2）不同点：
动态规划：每一步作一个选择—依赖于子问题的解。
贪心方法：每一步作一个选择—不依赖于子问题的解。
动态规划方法的条件：子问题的重叠性质。
可用贪心方法的条件：最优子结构性质；贪心选择性质。
动态规划：自底向上或自顶向下（备忘录方法）求解；
贪心方法：自顶向下求解。

0-1背包问题能不能用贪心算法求解？为什么？

对于部分背包问题,依照贪心选择策略,可以得到最优解。而0-1背包问题,贪心选择之所以不能得到最优解,是因为在这种情况下,它无法保证最终能将背包装满,部分闲置的背包空间使每公斤背包空间的价值降低了。因而我们选择的判断标准出现了误差。

例题：

重点：活动安排、背包问题、最优装载
单源最短路径、哈弗曼编码、最小生成树问题，重点理解贪心策略

第五章回溯法

回溯法的基本思想：

在问题的解空间树中，按深度优先策略，从根结点出发搜索解空间树。算法搜索至解空间树的任意一点时，先判断该结点是否包含问题的解。如果肯定不包含，则跳过对该结点为根的子树的搜索，逐层向其祖先结点回溯；否则，进入该子树，继续按深度优先策略搜索。

回溯法解题步骤

1. 针对所给问题，定义问题的解空间；
2. 确定易于搜索的解空间结构；
3. 以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。

用回溯法解题的特征：

在搜索过程中动态产生问题的解空间。问题的解空间树是虚拟的，并不需要在算法运行时构造一棵真正的树结构。在任何时刻，算法只保存从根结点到当前扩展结点的路径。

回溯法的算法框架：

递归回溯、子集树与排列树算法框架

影响回溯法的效率因素：

1. 产生x[k]的时间；
2. 满足显约束的x[k]值的个数；
3. 计算约束函数constraint的时间；
4. 计算上界函数bound的时间；
5. 满足约束函数和上界函数约束的所有x[k]的个数。

例题（看PPT）：

装载问题、n后问题、0-1背包问题、最大团问题、图的m着色问题、旅行售货员问题。
对每一个问题深刻理解以下几点：

1. 解的表示形式
2. 解空间表示成什么样的树型结构
3. 约束条件是什么？
4. 限界条件是什么（如果有的话）？
5. 如何构造并输出解。

第六章分支限界法

分支限界法的基本思想：

分支限界法常以广度优先或以最小耗费(最大效益)优先的方式搜索问题的解空间树。

分支限界法与回溯法的异同：

1)求解目旳:回溯法旳求解目旳是找出解空间树中满足约束条件旳所有解,而分支限界法旳求解目旳则是找出满足约束条件旳一种解,或是在满足约束条件旳解中找出在某种意义下旳最优解。
2)搜索方式旳不同:回溯法以深度优先旳方式搜索解空间树,而分支限界法则以广度优先或以最小耗费优先旳方式搜索解空间树。

分支限界法的实现方式：

队列式和优先队列式

例题：

单源最短路径、装载问题（重点）、0-1背包问题、旅行售货员问题。对于优先队列式分支限界法，重点理解堆元素的优先级怎么定，结点的上界或下界如何确定。

复习题库

选择题

1、二分搜索算法是利用（ A ）实现的算法。
A、分治策略 B、动态规划法 C、贪心法 D、回溯法
2、下列不是动态规划算法基本步骤的是（ A ）。
A、找出最优解的性质 B、构造最优解 C、算出最优解 D、定义最优解
3、最大效益优先是（ A ）的一搜索方式。
A、分支界限法 B、动态规划法 C、贪心法 D、回溯法
5. 回溯法解旅行售货员问题时的解空间树是（B ）。
A、子集树 B、排列树 C、深度优先生成树 D、广度优先生成树
6．下列算法中通常以自底向上的方式求解最优解的是（ B ）。
A、备忘录法 B、动态规划法 C、贪心法 D、回溯法
7、衡量一个算法好坏的标准是（C ）。
A 运行速度快 B 占用空间少 C 时间复杂度低 D 代码短
8、以下不可以使用分治法求解的是（D ）。
A 棋盘覆盖问题 B 选择问题 C 归并排序 D 0/1背包问题
9. 实现循环赛日程表利用的算法是（ A ）。
A、分治策略 B、动态规划法 C、贪心法 D、回溯法
11．下面不是分支界限法搜索方式的是（ D ）。
A、广度优先 B、最小耗费优先 C、最大效益优先 D、深度优先
12．下列算法中通常以深度优先方式系统搜索问题解的是（ D ）。
A、备忘录法 B、动态规划法 C、贪心法 D、回溯法
13.备忘录方法是那种算法的变形。（ B ）
A、分治法 B、动态规划法 C、贪心法 D、回溯法
14．哈弗曼编码的贪心算法所需的计算时间为（ B ）。
A、O（n2n） B、O（nlogn） C、O（2n） D、O（n）
15．分支限界法解最大团问题时，活结点表的组织形式是（ B ）。
A、最小堆 B、最大堆 C、栈 D、数组
16．最长公共子序列算法利用的算法是（ B ）。
A、分支界限法 B、动态规划法 C、贪心法 D、回溯法
17．实现棋盘覆盖算法利用的算法是（ A ）。
A、分治法 B、动态规划法 C、贪心法 D、回溯法
18.下面是贪心算法的基本要素的是（ C ）。
A、重叠子问题 B、构造最优解 C、贪心选择性质 D、定义最优解
19.回溯法的效率不依赖于下列哪些因素（ D ）
A.满足显约束的值的个数 B. 计算约束函数的时间
C. 计算限界函数的时间 D. 确定解空间的时间
20.下面哪种函数是回溯法中为避免无效搜索采取的策略（ B ）
A．递归函数 B.剪枝函数 C。随机数函数 D.搜索函数
21、下面关于NP问题说法正确的是（B ）
A NP问题都是不可能解决的问题
B P类问题包含在NP类问题中
C NP完全问题是P类问题的子集
D NP类问题包含在P类问题中
24. （D ）是贪心算法与动态规划算法的共同点。
A、重叠子问题 B、构造最优解 C、贪心选择性质 D、最优子结构性质
25. 矩阵连乘问题的算法可由（ B）设计实现。
A、分支界限算法 B、动态规划算法 C、贪心算法 D、回溯算法
26. 分支限界法解旅行售货员问题时，活结点表的组织形式是（ A ）。
A、最小堆 B、最大堆 C、栈 D、数组
27、Strassen矩阵乘法是利用（ A ）实现的算法。
A、分治策略 B、动态规划法 C、贪心法 D、回溯法
29、使用分治法求解不需要满足的条件是（A ）。
A 子问题必须是一样的
B 子问题不能够重复
C 子问题的解可以合并
D 原问题和子问题使用相同的方法解
30、下面问题（B ）不能使用贪心法解决。
A 单源最短路径问题 B N皇后问题
C 最小花费生成树问题 D 背包问题
31、下列算法中不能解决0/1背包问题的是（A ）
A 贪心法 B 动态规划 C 回溯法 D 分支限界法
34．实现合并排序利用的算法是（ A ）。
A、分治策略 B、动态规划法 C、贪心法 D、回溯法
35．下列是动态规划算法基本要素的是（ D ）。
A、定义最优解 B、构造最优解 C、算出最优解 D、子问题重叠性质
37．采用广度优先策略搜索的算法是（ A ）。
A、分支界限法 B、动态规划法 C、贪心法 D、回溯法
38、合并排序算法是利用（ A ）实现的算法。
A、分治策略 B、动态规划法 C、贪心法 D、回溯法
40、背包问题的贪心算法所需的计算时间为（ B ）
A、O（n2n） B、O（nlogn） C、O（2n） D、O（n）
41．实现大整数的乘法是利用的算法（ C ）。
A、贪心法 B、动态规划法 C、分治策略 D、回溯法
42．0-1背包问题的回溯算法所需的计算时间为（ A ）
A、O（n2n） B、O（nlogn） C、O（2n） D、O（n）
43．采用最大效益优先搜索方式的算法是（ A ）。
A、分支界限法 B、动态规划法 C、贪心法 D、回溯法
44．贪心算法与动态规划算法的主要区别是（ B ）。
A、最优子结构 B、贪心选择性质 C、构造最优解 D、定义最优解
45. 实现最大子段和利用的算法是（ B ）。
A、分治策略 B、动态规划法 C、贪心法 D、回溯法
46.优先队列式分支限界法选取扩展结点的原则是（ C ）。
A、先进先出 B、后进先出 C、结点的优先级 D、随机
47.背包问题的贪心算法所需的计算时间为（ B ）。
A、O（n2n） B、O（nlogn） C、O（2n） D、O（n）
48、广度优先是（ A ）的一搜索方式。
A、分支界限法 B、动态规划法 C、贪心法 D、回溯法
52. 一个问题可用动态规划算法或贪心算法求解的关键特征是问题的（ B ）。
A、重叠子问题 B、最优子结构性质 C、贪心选择性质 D、定义最优解
53．采用贪心算法的最优装载问题的主要计算量在于将集装箱依其重量从小到大排序，故算法的时间复杂度为 ( B ) 。
A、O（n2n） B、O（nlogn） C、O（2n） D、O（n）
54. 以深度优先方式系统搜索问题解的算法称为 ( D ) 。
A、分支界限算法 B、概率算法 C、贪心算法 D、回溯算法
55. 实现最长公共子序列利用的算法是（ B ）。
A、分治策略 B、动态规划法 C、贪心法 D、回溯法

填空题

1.算法的复杂性有 时间 复杂性和 空间 复杂性之分。
2、程序是 算法 用某种程序设计语言的具体实现。
3、算法的“确定性”指的是组成算法的每条 指令 是清晰的，无歧义的。
4.矩阵连乘问题的算法可由 动态规划 设计实现。
6、算法是指解决问题的 一种方法 或 一个过程 。
7、从分治法的一般设计模式可以看出，用它设计出的程序一般是 递归算法 。
8、问题的 最优子结构性质 是该问题可用动态规划算法或贪心算法求解的关键特征。
9、以深度优先方式系统搜索问题解的算法称为 回溯法 。
11、计算一个算法时间复杂度通常可以计算 循环次数 、 基本操作的频率 或计算步。
14、解决0/1背包问题可以使用动态规划、回溯法和分支限界法，其中不需要排序的是 动态规划 ，需要排序的是 回溯法 ，分支限界法 。
15、使用回溯法进行状态空间树裁剪分支时一般有两个标准：约束条件和目标函数的界，N皇后问题和0/1背包问题正好是两种不同的类型，其中同时使用约束条件和目标函数的界进行裁剪的是 0/1背包问题 ，只使用约束条件进行裁剪的是 N皇后问题 。
16、 贪心选择性质 是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。
17、矩阵连乘问题的算法可由 动态规划 设计实现。
19.贪心算法的基本要素是 贪心选择 质和 最优子结构 性质 。
21. 动态规划算法的基本思想是将待求解问题分解成若干 子问题 ，先求解 子问题 ，然后从这些 子问题 的解得到原问题的解。
22.算法是由若干条指令组成的有穷序列，且要满足输入、 输出 、确定性和 有限性 四条性质。
23、大整数乘积算法是用 分治法 来设计的。
24、以广度优先或以最小耗费方式搜索问题解的算法称为 分支限界法 。
26、 贪心选择性质 是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。
27.快速排序算法是基于 分治策略 的一种排序算法。
28.动态规划算法的两个基本要素是. 最优子结构 性质和 重叠子问题 性质 。
30.回溯法是一种既带有 系统性 又带有 跳跃性 的搜索算法。
31.分支限界法主要有 队列式（FIFO） 分支限界法和 优先队列式 分支限界法。
32．分支限界法是一种既带有 系统性 又带有 跳跃性 的搜索算法。
33．回溯法搜索解空间树时，常用的两种剪枝函数为 约束函数 和 限界函数 。
34.任何可用计算机求解的问题所需的时间都与其 规模 有关。
35.快速排序算法的性能取决于 划分的对称性 。

算法填空

1.背包问题的贪心算法

void Knapsack(int n, float M, float v[], float w[], float x[])
{
      Sort(n, v, w);//排序
      int i;
      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;//否则改变物品状态为1 表示已经选择
          c - = w[i];//背包剩余容量改变 
    	}
   if (i <= n) x[i] = c / w[i];//如果没有装完物品的话，能装多少装多少
}
 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

2.最大子段和 动态规划算法

int MaxSum(int n, int a[])
{
    int sum = 0, b = 0; //sum用来表示最大值 b用来当做目前的子段和
    for (int j = 1;j <= n;j++)
    {
        if(b > 0) b += a[j]; //如果b大于0，那么就加上当前的 
        else b = a[j];//否则就等于当前的
        if (b > sum)//如果b比sum大的话 那么sum就赋值为b
            sum = b;
    }
    return sum;
}   
1
2
3
4
5
6
7
8
9
10
11
12

3.贪心算法求装载问题

template <class Type>
void Loading(int x[], Type w[], Type c, int n)
{
    int *t = new int[n + 1];
    Sort(w, t, n) 
    for (int i = 1; i <= n; i++) x[i] = 0;
    for (int i = 1; i <= n && w[t[i]] <= c; i++)
    {
        x[t[i]] = 1;
        c -= w[t[i]];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12

4.贪心算法求活动安排问题

template <class Type>
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;//不选这个活动
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

5.快速排序

核心思想是二分

template <class Type>
void QuickSort(Type a[], int p, int r)
{
    if (p < r)
    {
        Int q = Partition(a, p, r);
        QuickSort(a, p, q - 1); // 对左半段排序
        QuickSort(a, q + 1, r); // 对右半段排序
    }
}
1
2
3
4
5
6
7
8
9
10

6.排列问题

Template<class Type> void perm(Type list[], int k, int m)
{
    if (k == m)
    { // 只剩下一个元素 直接输出列表元素0~m
        for (int i = 0; i <= m; i++)
            cout << list[i];
        cout << endl;
    }
    else // 还有多个元素待排列，递归产生排列
        for (int i = k; i <= m; i++)//从k到m
        {
            swap(list[k],list[i]);//交换k i元素
            perm(list, k + 1, m);//排列 k+1~m
            swap(list[k], list[i]);//再换回来
        }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

7.用回溯法搜索子集树的算法为：

void backtrack(int t)
{
    if (t > n)
        output(x);//大于节点数了，直接输出x
    else
        for (int i = 0; i <= 1; i++)
        {
            x[t] = i;
            if (constraint(t) && bound(t))
                backtrack(t + 1);
        }
}

1
2
3
4
5
6
7
8
9
10
11
12
13

简答题

1.分治法的基本思想：

将一个规模为n的问题分解为k个规模较小的子问题，这些子问题互相独立且与原问题相同。递归地解这些子问题，然后将各个子问题的解合并得到原问题的解。

2.设计动态规划算法的主要步骤为：

（1）找出最优解的性质，并刻画其结构特征。（2）递归地定义最优值。
（3）以自底向上的方式计算出最优值。（4）根据计算最优值时得到的信息，构造最优解。

3. 分治法与动态规划法异同

相同点是：将待求解的问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。
不同点是：适合于用动态规划法求解的问题，经分解得到的子问题往往不是互相独立的。而用分治法求解的问题，经分解得到的子问题往往是互相独立的。

4. 分支限界法与回溯法异同

相同点：都是一种在问题的解空间树T中搜索问题解的算法。
不同点：（1）求解目标不同（2）搜索方式不同（3）对扩展结点的扩展方式不同（4）存储空间的要求不同。

5.贪心算法与动态规划算法的主要区别

所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。这是利用贪心算法求解最优解的第一个基本要素，也是贪心算法与动态规划算法的主要区别。
共同点：
求解的问题都具有最优子结构性质
差异点：
动态规划算法通常以自底向上的方式解各子问题，而贪心算法则通常以自顶向下的方式进行，以迭代的方式作出相继的贪心选择，每做一次贪心选择就将所求问题简化为规模更小的子问题。

6. 分治法所能解决的问题一般具有的几个特征是：

（1）该问题的规模缩小到一定的程度就可以容易地解决；
（2）该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质;
（3）利用该问题分解出的子问题的解可以合并为该问题的解；
（4）原问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。

7. 用分支限界法设计算法的步骤是：

(1)针对所给问题，定义问题的解空间（对解进行编码）(2)确定易于搜索的解空间结构（按树或图组织解）；(3)以广度优先或以最小耗费（最大收益）优先的方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。

8. 常见的两种分支限界法的算法框架

（1）队列式(FIFO)分支限界法：按照队列先进先出原则选取下一个节点为扩展节点。
（2）优先队列式分支限界法：按照优先队列中规定的优先级选取优先级最高的节点成为当前扩展节点。

9. 回溯法中常见的两类典型的解空间树：

子集树：当所给的问题是从n个元素的集合S中找出满足某种性质的子集时，相应的解空间树称为子集树。这类子集树通常有2n个叶结点，遍历子集树需O(2n)计算时间 。
排列树：当所给的问题是确定n个元素满足某种性质的排列时，相应的解空间树称为排列树。这类排列树通常有n!个叶结点。遍历排列树需要O(n!)计算时间。

10. 分支限界法的搜索策略是：

在扩展结点处，先生成其所有的儿子结点（分支），然后再从当前的活结点表中选择下一个扩展结点。为了有效地选择下一扩展结点，加速搜索的进程，在每一个活结点处，计算一个函数值（限界），并根据函数值，从当前活结点表中选择一个最有利的结点作为扩展结点，使搜索朝着解空间上有最优解的分支推进，以便尽快地找出一个最优解。

11、回溯法的基本思想

是在一棵含有问题全部可能解的状态空间树上进行深度优先搜索，解为叶子结点。搜索过程中，每到达一个结点时，则判断该结点为根的子树是否含有问题的解，如果可以确定该子树中不含有问题的解，则放弃对该子树的搜索，退回到上层父结点，继续下一步深度优先搜索过程。在回溯法中，并不是先构造出整棵状态空间树，再进行搜索，而是在搜索过程，逐步构造出状态空间树，即边搜索，边构造。

算法设计题

1. 给定已按升序排好序的n个元素a[0:n-1]，现要在这n个元素中找出一特定元素x，返回其在数组中的位置，如果未找到返回-1。
   写出二分搜索的算法，并分析其时间复杂度。

template <class Type>
int BinarySearch(Type a[], const Type &x, int n)
{ // 在a[0:n]中搜索x，找到x时返回其在数组中的位置，否则返回-1
    int left = 0;
    int right = n - 1;
    while(left <= right)
    {
        int middle = (left + right) / 2;//找到中点
        if (x == a[middle])//如果找到了 返回
            return middle;
        if (x > a[middle])//如果大于 那就在右边找
            left = middle + 1;
        else //如果小于 那就在左边找
            right = middle - 1;
    }
    Return - 1;//没找到 返回-1
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

时间复杂性为O(logn)

2. 利用分治算法写出合并排序的算法，并分析其时间复杂度

void MergeSort(Type a[], int left, int right)
{
    if (left < right)
    {                               // 至少有2个元素
        int i = (left + right) / 2; // 取中点
        mergeSort(a, left, i);//左侧合并排序
        mergeSort(a, i + 1, right);//右侧合并排序
        merge(a, b, left, i, right); // 合并到数组b
        copy(a, b, left, right);     // 复制回数组a
    }
}
1
2
3
4
5
6
7
8
9
10
11

算法在最坏情况下的时间复杂度为O(nlogn)。

3.N皇后回溯法

bool Queen::Place(int k)
{ // 检查x[k]位置是否合法
    for (int j = 1; j < k; j++)
        if ((abs(k - j) == abs(x[j] - x[k])) || (x[j] == x[k]))
            return false;
    return true;
}

void Queen::Backtrack(int t)
{
    if (t > n)
        sum++;
    else
        for (int i = 1; i <= n; i++)
        {
            x[t] = i;
            if (约束函数)
                Backtrack(t + 1);
        }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

4.最大团问题 回溯法

void Clique::Backtrack(int i) // 计算最大团
{
    if (i > n)
    { // 到达叶结点
        for (int j = 1; j <= n; j++)
        	bestx[j] = x[j];
        bestn = cn;
        return;
    }
    // 检查顶点 i 与当前团的连接
    int OK = 1;
    for (int j = 1; j < i; j++)
        if (x[j] && a[i][j] == 0)
        { // i与j不相连
            OK = 0;
            break;
        }
    if (OK)
    { // 进入左子树
        x[i] = 1;
        cn++;
        Backtrack(i + 1);
        x[i] = 0;
        cn--;
    }
    if (cn + n - i > bestn)
    { // 进入右子树
        x[i] = 0;
        Backtrack(i + 1);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

5.最长公共子序列问题

// 参数:x字符串长度为m y字符串长度为n
void LCSLength(char x[], char y[], int m, int n)
{
    /* 计算最长公共子序列的长度 */
    int L[m][n], i，j;
    for (i = 0; i <= m; i++)
        L[i][0] = 0;
    for (i = 0; i <= n; i++)
        L[0][i] = 0;
    for (i = 1; i <= m; i++)
    {
        for (j = 1; j <= n; j++)
        {
            if (x[i] == y[j])
                L[i][j] = L[i - 1][j - 1] + 1;
            else if (L[i - 1][j] >= L[i][j - 1])
                L[i][j] = L[i - 1][j];
            else
                L[i][j] = L[i][j - 1];
        }
    }
    return L[m][n];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

6.分别用贪心算法、动态规划法、回溯法设计0-1背包问题。要求：说明所使用的算法策略；写出算法实现的主要步骤；分析算法的时间。
（1）贪心算法 O（nlog（n））
首先计算每种物品单位重量的价值Vi/Wi，然后，依贪心选择策略，将尽可能多的单位重量价值最高的物品装入背包。若将这种物品全部装入背包后，背包内的物品总重量未超过C，则选择单位重量价值次高的物品并尽可能多地装入背包。依此策略一直地进行下去，直到背包装满为止。

void Knapsack(int n, float M, float v[], float w[], float x[])
{
    sort(n, v, w);
    int i;
    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];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

（2）动态规划法 O(nc)
m(i，j)是背包容量为j，可选择物品为i，i+1，…，n时0-1背包问题的最优值。由0-1背包问题的最优子结构性质，可以建立计算m(i，j)的递归式如下。

void KnapSack(int v[], int w[], int c, int n, int m[][11])
{
    int jMax = min(w[n] - 1, c);
    for (j = 0; j <= jMax; j++) /*m(n,j)=0   0=<j<w[n]*/
        m[n][j] = 0;
    for (j = w[n]; j <= c; j++) /*m(n,j)=v[n]   j>=w[n]*/
        m[n][j] = v[n];
    for (i = n - 1; i > 1; i--)
    {
        int jMax = min(w[i] - 1, c);
        for (j = 0; j <= jMax; j++) /*m(i,j)=m(i+1,j)   0=<j<w[i]*/
            m[i][j] = m[i + 1][j];
        for (j = w[i]; j <= c; j++) /*m(n,j)=v[n]   j>=w[n]*/
            m[i][j] = max(m[i + 1][j], m[i + 1][j - w[i]] + v[i]);
    }
    m[1][c] = m[2][c];
    if (c >= w[1])
        m[1][c] = max(m[1][c], m[2][c - w[1]] + v[1]);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

（3）回溯法 O(2n)
cw:当前重量 cp:当前价值 bestp：当前最优值

void backtrack(int i)
// 回溯法 i初值1
{
    if (i > n) // 到达叶结点
    {
        bestp = cp;
        return;
    }
    if (cw + w[i] <= c) // 搜索左子树
    {
        cw += w[i];
        Cp += p[i];
        backtrack(i + 1);
        cw -= w[i];
        cp -= p[i];
    }
    if (Bound(i + 1) > bestp)
        // 搜索右子树
        backtrack(i + 1);
      
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

7.通过键盘输入一个高精度的正整数n(n的有效位数≤240)，去掉其中任意s个数字后，剩下的数字按原左右次序将组成一个新的正整数。编程对给定的n 和s，寻找一种方案，使得剩下的数字组成的新数最小。
【样例输入】
178543
S=4
【样例输出】
13
为了尽可能地逼近目标，我们选取的贪心策略为：每一步总是选择一个使剩下的数最小的数字删去，即按高位到低位的顺序搜索，若各位数字递增，则删除最后一个数字，否则删除第一个递减区间的首字符。然后回到串首，按上述规则再删除下一个数字。重复以上过程s次，剩下的数字串便是问题的解了。
具体算法如下：

输入s, n;
while（ s > 0 ）
{
    i = 1; // 从串首开始找
    while (i < length(n)&&(n[i] < n[i + 1])
        {
            i++;
        }
    delete (n, i, 1); // 删除字符串n的第i个字符
    s--;
}
while (length(n) > 1)&&(n[1] =‘0’) delete(n, 1, 1); // 删去串首可能产生的无用零
输出n;
1
2
3
4
5
6
7
8
9
10
11
12
13