算法设计与分析学习笔记

一、课程主要内容

二、本节课的主要内容

三、算法设计的要点

四、本节课涉及的问题

货郎问题
0-1背包问题
双机调度问题
NP-hard问题

.......

五、货郎问题

注：课后作业要用到。

六：算法的两种时间复杂度

最坏时间复杂度和平均时间复杂度。

七、算法的伪代码描述

八、函数的渐近的界

大O符号（描述一个函数的“上界”）

Ω符号（描述一个函数的“下界”）

小o符号（描述一个更“严格”的上界）

小w符号（描述一个更“严格”的下界）

课后作业

用python或java简单实现货郎问题(TSP,Traveling Salesman Problem)。

from itertools import permutations  # 导入排列函数

# 定义城市和它们之间的距离
cities = ["c1", "c2", "c3", "c4"]
distances = {
    ("c1", "c2"): 10,
    ("c1", "c3"): 5,
    ("c1", "c4"): 9,
    ("c2", "c3"): 6,
    ("c2", "c4"): 9,
    ("c3", "c4"): 3,
}


# 函数：计算给定路径的总距离
def calculate_distance(path, distances):
    total_distance = 0  # 初始化总距离为0
    for i in range(len(path) - 1):  # 遍历路径中的每一对相邻城市
        # 使用get方法从字典中提取城市对的距离，如果没有则尝试反向城市对
        total_distance += distances.get(
            (path[i], path[i + 1]), distances.get((path[i + 1], path[i]), 0)
        )
    return total_distance  # 返回总距离


# 生成所有可能的路径（排列）
all_paths = list(permutations(cities))

# print(all_paths)
# print(len(all_paths))

# 寻找具有最小距离的路径
min_distance = float("inf")  # 初始化最小距离为无穷大
min_path = None  # 初始化最短路径为None

# 遍历所有可能的路径
for path in all_paths:
    path_with_return = path + (path[0],)  # 在路径末尾添加起始城市，形成一个回路
    distance = calculate_distance(path_with_return, distances)  # 计算回路的总距离
    if distance < min_distance:  # 如果找到更短的路径，则更新最小距离和最短路径
        min_distance = distance
        min_path = path_with_return

# 输出最短路径和其总距离
print(min_path, min_distance)

九、补充

教材—算法设计与分析（第2版）

一、θ符号（同阶）

二、小w符号（描述算法复杂性的渐进下界）

三、有关函数渐近的界的定理（定理1）

四、一些重要的结果

五、有关函数渐近的界的定理（定理2）

六、有关函数渐近的界的定理（定理3）

七、小结

八、基本函数类

九、对数函数

十、指数函数和阶乘

十一、取整函数

十二、取整函数的性质

十三、例题，按照阶排序

十四、数列求和公式

十五、二分检索平均时间复杂度

一、国庆作业

汉诺塔（港台：河内塔）（Tower of Hanoi）是根据一个传说形成的数学问题：

有三根杆子A，B，C。A杆上有 N 个 (N>1) 穿孔圆盘，盘的尺寸由下到上依次变小。要求按下列规则将所有圆盘移至 C 杆：

每次只能移动一个圆盘；大盘不能叠在小盘上面。

解题思路：

#include <stdio.h>

// 汉诺塔递归函数
void hanoi(int n, char A, char B, char C) {
    // 当只有一个盘子时，直接从 A 移动到 C
    if (n == 1) {
        printf("Move disk 1 from %c to %c\n", A, C);
        return;
    }
    // 先将 n-1 个盘子从 A 移动到 B，以 C 作为中间塔
    hanoi(n-1, A, C, B);
    // 移动第 n 个盘子从 A 到 C
    printf("Move disk %d from %c to %c\n", n, A, C);
    // 最后将 n-1 个盘子从 B 移动到 C，以 A 作为中间塔
    hanoi(n-1, B, A, C);
}

int main() {
    // 初始化盘子数量为 3
    int n = 3;
    // 输出汉诺塔移动步骤
    printf("Hanoi Tower moves:\n");
    // 调用 hanoi 函数进行汉诺塔问题求解
    hanoi(n, 'A', 'B', 'C');
    return 0;
}

汉诺塔问题时间复杂度的分析：

插入排序的重要性质：

#include <stdio.h>

// 插入排序函数
void insertionSort(int arr[], int n) {
    int i, j, key;
    // 从数组的第二个元素开始遍历
    for (i = 1; i < n; i++) {
        // 当前待排序的元素
        key = arr[i];
        // 找到 key 应该插入的位置
        j = i - 1;
        // 将比 key 大的元素向后移动
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        // 将 key 插入到正确的位置
        arr[j + 1] = key;
    }
}

// 打印数组函数
void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

int main() {
    // 初始化一个待排序的数组
    int arr[] = {12, 11, 13, 5, 6};
    // 计算数组长度
    int n = sizeof(arr) / sizeof(arr[0]);

    // 打印原始数组
    printf("Original array: \n");
    printArray(arr, n);

    // 进行插入排序
    insertionSort(arr, n);

    // 打印排序后的数组
    printf("Sorted array: \n");
    printArray(arr, n);

    return 0;
}

一、估计和式上界的放大法

二、估计和式渐近的界

三、递推方程

四、迭代法求解递推方程

换元迭代：

五、差消法化简高阶递推方程

六、递归树

一种用于分析递归算法时间复杂度的工具。它将递归过程展现为一棵树，从而我们可以很直观地看到每个递归层级的运算量。

七、主定理

八、GPT关于主定理的例子和解释

九、主定理求解递归式的好处

一、无法使用主定理求解递推方程时，可以使用递归树求解。

二、主定理求解递推方程的条件 && 主定理什么时候可以用？

三、大O符号表示小于等于

四、典型的分治算法

五、分治策略的基本思想

六、分治算法的特点

七、两类常见的递推方程及其求解

八、方程2的解

九、芯片测试的分治算法

十、分治策略中的快速排序

课后作业：习题一

一、斐波那契数列的性质

二、幂乘算法小结

三、改进分治算法的途径1：减少子问题数

减少子问题个数的依据

矩阵乘法的研究及应用和改进途径小结

四、改进分治算法的途径2：增加预处理

五、选最大与最小

六、选第二大

选第二大提高效率的途径

七、一般选择问题的算法设计

选择第k小的算法：

八、选择问题的算法分析

九、为啥选择第k小的算法，采用分治方法，分组时5个元素一组？3个元素一组或7个一组行不行？

注：算法设计与分析课程更改到每周一下午567节课。地点：学友楼504

课堂作业

按课本实践。

一、动态规划算法的例子

动态规划算法中的算法设计

优化原则

注：

不满足优化原则，不能用动态规划。
动态规划图中的u和d，分别代表up和down。

小结：

二、动态规划算法设计

矩阵相乘基本运算次数

动态规划算法和优化函数的递推方程

小结

三、动态规划算法的递归实现

四、动态规划算法的迭代实现

迭代算法的关键

备忘录和标记函数

如何理解标记函数和备忘录

递归实现动态规划算法和迭代实现动态规划算法两种实现的比较，及动态规划算法的要素

动态规划（Dynamic Programming）

1、课堂关键字

最长公共子序列5.8

一、爬楼梯问题—动态规划

二、扑克牌问题

1、课堂关键字

贪心法的设计思想4.1~对贪心法得不到最优解情况的处理4.3

2、课后作业

田忌赛马研究如何构造贪心策略，做PPT讲解思路。

1、预习作业

2、预习作业

leetcode 51
百练poj 2754

1、课堂关键字

回溯算法
0-1背包问题

2、预习作业

1、课堂要点

线性规划模型
整数线性规划的分支限界算法

2、预习作业

第7章 网络流算法

7.1 最大流问题
（*）7.1.1 网络流及其性质
（9）7.1.1 Ford-Fulkerson算法
（8）7.1.1 Dinic有效算法

7.2 最小流问题
（7）7.2.1 Floyd算法
（6）7.2.2 最小费用的负回路算法
（5）7.2.3 最小费用的最短路径算法

7.3 运输问题
（4）7.3.1 确定初始调运方案
（3）7.3.2 改进调运方案
（2）7.3.3 表上作业法

7.4 二部图匹配
（1）7.4.1 二部图的最大匹配
（0）7.4.2 赋权二部图的匹配

按（学号最后两位%10）的准备相关内容（PPT+讲解）
（*）：全员准备

1、课堂关键字

网络流算法

2、课后作业

第8章 算法分析与问题的计算复杂度

（*）8.1 平凡下界

（*）8.2 直接计数求解该问题所需要的最少运算

（*）8.3 决策树

（3）8.4 检索算法的时间复杂度分析

        8.5 排序算法的时间复杂度
（2）8.5.1 冒泡排序算法
（1）8.5.2 堆排序算法
（0）8.5.3 排序算法的决策树与算法累时间复杂度的下界

        8.6 选择算法的时间复杂度分析
（1）8.6.1 找最大和最小问题
（2）8.6.2 找第二大问题
（3）8.6.3 找中位数的问题

（0）8.7 通过规约确认问题计算复杂度的下界


按（座位号%4）准备相关内容（PPT+讲解）
（*）：全员准备
%：“求余”运算

3、期末考试形式：笔试

1、课堂关键字

算法分析与问题的计算复杂度

2、预习作业

第9章 NP完全性

（*）9.1 P类与NP类
        9.1.1 易解的问题与难解的问题
        9.1.2 判定问题
        9.1.3 NP类

（6）9.2 多项式实践变换与NP完全性
         9.2.1 多项式时间变换
         9.2.2 NP完全性及其性质
         9.2.3 Cook-Levin定理--第一个NP完全问题

        9.3 几个NP完全问题
（3）9.3.1 最大可满足性与三元可满足行
（2）9.3.2 定点覆盖、团与独立集
（1）9.3.3 哈密顿回路与货郎问题
（0）9.3.4 恰好覆盖
（5）9.3.5 子集和、背包、装箱与双机调度
（4）9.3.6 整数线性规划

按（座位号%7）的准备相关内容（PPT+讲解）
（*）：全员准备
%：“求余”运算

1、课堂关键字

NP完全性

2、提及到的期末复习考察重点

分治问题
动态规划，状态转移方程
贪心算法
时间复杂度
6～9
期末会有难题：算法推导与实现

基础知识学习笔记

1、如果函数f(n)的渐近的上界和下界相等，都是g(n)，这时称g(n)是f(n)的渐近的紧的界，或者称函数f(n)的阶是g(n)。同阶可称g(n)是f(n)的紧的界。

2、大O记号和小o记号的区别：

当f(n)=O(g(n))时，f(n)的阶可能低于g(n)的阶，也可能等于g(n)的阶，而f(n)=o(g(n))时，f(n)的阶只能低于g(n)的阶。因此f(n)=o(g(n))可以推出f(n)=O(g(n))，但是反过来不成立。

3、主定理

4、指数函数的阶高于多项式函数的阶，而多项式函数的阶高于对数函数的阶。

5、在没有明确说明的情况下，算法课程中的 "log n" 通常意味着二进制对数。

6、在使用主定理（Master Theorem）来分析递归算法的时间复杂度时，我们关注的是当问题规模n趋向于无穷大时，时间复杂度 T(n)的渐近行为。

7、递推方程不满足主定理的条件，可以使用递归树求解。

8、在递归算法的时间复杂度分析中常常用到主定理，其中a代表递归调用所产生的字问题个数，n/b代表这些字问题的规模，f(n)则代表调用前的操作及调用后把子问题的解组合成原问题的解的总工作量。

9、递归树方法：

首先将复杂度的递归式展开树的形式
之后，计算树每层的复杂度
最后，将所有层的复杂度相加，得到T（n）的复杂度

10、复杂度的递归求解

1.展开法：通过直接对递归的展开计算复杂度；
2.代入法：先猜测解的形式，再通过数学归纳浅证明；
3.递归树方法：通过画递归树的方法来求解，因这种方法适用性比较好，所以是最重要的方法；
4.主方法针对T（n）=aT（n/b）+f（n）的形式，主方法给出了相关的规律，所以主方法是最简单的方法（套规律就行），但因只能针对上面形式的递归式，所以适用性较差。

分治算法学习笔记

1、分治算法的设计思想：

分治法的设计思想，大事化小，名个击破，分而治之。将难以直接解决的大问题，分割成一些规模较小的子问题，子问题相互独立并与原问题相同，以便各个击破，分为治之。

2、分治算法的基本思想

分解为子问题
求解子问题
合并得到原问题的解

3、分治法的适用条件

4、分治算法的改进方法

减少子问题的个数
改进分治的均衡度
减少合并的时间

5、分治算法选择题

解析：

在分治法中，通常我们说的“相同”指的是解决问题的方法或过程是相同的，而不一定是子问题在所有方面都完全相同。

例如，在归并排序中，我们将数组分成两半进行排序，这两半的排序过程是相同的，但它们可能包含不同的元素。

6、分治算法的三个过程

划分
递归地求解
合并

7、分治算法时间复杂度分析的方法

可以用递归树来分析分治算法的时间复杂度。

8、分治法是将一个难以直接求解的复杂问题分解成若干个规模较小、相互独立且类型相同的子问题，然后求解这些子问题，直到子问题足够小能够直接求解，再将子问题的解组合成原始问题的完整答案。

动态规划学习笔记

1、动态规划就是：给定一个问题，我们把它拆成一个个子问题，直到子问题可以直接解决。然后把子问题的答案保存起来，以减少重复计算。再根据子问题答案反推，得出原问题解的一种方法。

关键词

记忆化搜索（备忘录）

2、动态规划入门思路：dfs暴力—>记忆化搜索—>动态规划（递推）

3、递归的过程：“归”的过程才是产生答案的过程，“递”的过程是分解子问题的过程。

4、

“递"--> 自顶向下

“归”--> 自底向上

5、递归搜索树的底是已知最小子问题的答案。

6、

记忆化搜索 = 暴力dfs +记录答案

递推的公式= dfs 向下递归的公式

递推数组的初始值 = 递归的边界

7、动态规划，偏向全局最优，贪心法偏向局部最优。

8、以下关于动态规划法的描述哪些是正确的？

A.将问题分解成多级或许多子问题，然后顺序求解子问题。

B.可以确保得到最佳解

C.前一个子问题的解为后一个子问题的求解提供有用的信息。

D.从问题某一初始或推测值出发，一步步的攀登给定目标。

E.尽可能快的去逼近更好的解，当达到某一步不能继续时终止。

答案：A、C、D、E

链接：https://www.nowcoder.com/questionTerminal/ad0b237fcfe1468fb8fdb24b135586ae

9、动态规划入门习题

https://www.luogu.com.cn/paste/xac615na

10、动态规划的基本思想：

保存已解决的子问题结果，在需要时直接使用已求得的结果，避免大量重复计算，从而得到多项式时间算法。一记忆法

11、分治法 vs 动态规划法

相同：

原问题分解为子问题，求解子问题，得到原问题的解
前后存在递推关系

不同：

对分治算法，要求子问题独立；对动态规划，要求子问题重叠。

12、贪心、分治、动态规划

贪心：逐步构造解，以局部最优的贪婪准则构造。
分治：把原问题分为子问题，解决子问题，合并得到原问题的解。
动态规划：把原问题分为交叉的子问题。解决子问题，记录子问题的解，合并为原问题的解。

13、记忆化搜索（备忘录）vs 动态规划

例子：

14、动态规划基本要素

最优子结构性质：原问题的最优解包含子问题的最优解
重叠子问题性质：递归算法求解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次
无后效性：问题的全过程可以分为若干个阶段，而且在任何一个阶段x后的行为都只仅仅依赖于x的状态，而与x之前如何达到这种状态的方式无，这样的过程就构成了一个多阶段决策过程。未来与过去无关。

15、

贪心算法

最优子结构
无后效性
贪心选择

动态规划

最优子结构
无后效性
子问题重叠

16、动态规划算法的求解步骤

17、动态规划课后习题

18、0-1背包、恰好装满的0-1背包、完全0-1背包、多重0-1背包

0-1背包问题：选择物品放入固定容量的背包，以最大化价值，每个物品只能选或不选。
恰好装满的0-1背包问题：在0-1背包的基础上，要求背包被恰好装满。
完全0-1背包问题：每种物品可以选无限多个。
多重0-1背包问题：每种物品有数量限制。

19、动态规划策略通常用于求解最优化问题。在这类问题中，可能会有许多可行解。每一个解都对应于一个值，我们希望找到具有最优值的那个解，即最优解。

20、动态规划算法的基本步骤

a.分析最优解的结构

b.递归定义最优值

c.计算最优值

d.构造最优解

贪心法学习笔记

1、田忌赛马问题

2、贪心算法：

依贪婪准则作出决策，逐步构造解值。又叫登山法，根本思想是逐步到达山顶，即局部最优逐步达到全局最优。

3、贪心算法的特点：

4、贪心算法的三个性质

最优子结构

a.原问题的最优解包含其子问题的最优解

b.问题的最优子结构性质是该问题可用贪心算法或动态规划算法求解的关键特征。

贪心选择

a.通过一系列局部最优的选择（贪心选择）达到全局最优

b.这是贪心算法与动态规划算法的主要区别

无后效性

问题的全过程可以分为若干个阶段，而且在任何一个阶段x后的行为都只仅仅依赖于x的状态，而与x之前如何达到这种状态的方式无关。这样的过程就构成了一个多阶段决策过程。

5、贪心法处理问题的核心是贪婪准则的选取，难点是最优解的证明。

6、背包问题课后习题

7、基本要素课后习题

8、MST课后习题

9、哈夫曼编码课后习题

回溯法学习笔记

1、回溯法被称为具有剪枝函数的深度优先生成法。

2、剪枝函数

可行性约束函数
上界函数

3、排列树、子集树、解空间树

4、

下列哪个结点属于回溯法的结点类型？（）

A.扩展结点
B.活结点
c.收缩结点
D.死结点
正确答案：A、B、D
解析：
在回溯算法中，结点类型的理解是关键。这个问题涉及到三种类型的结点：扩展结点、活结点和死结点。
让我们一一解释这些术语，以便更好地理解。

扩展结点（A）
扩展结点是指当前正在考察的结点。在回溯算法中，当我们到达一个新结点，并且正在探索从这个结点出
发的所有可能的分支时，这个结点被称为扩展结点。简单来说，扩展结点就是当前的焦点或工作结点。

活结点（B）
活结点是指那些已经被部分探索过，但其子结点还没有被完全探索的结点。这意味着从这个结点出发可能
还存在到达解的路径。在回溯过程中，如果一个结点还未被完全排除（即仍然有可能通向解），它就是一个活结点。

收缩结点
这个选项在回溯算法的常用术语中并不常见，可能是个错误的选项或者是对其他术语的不标准表述。

死结点（D）
死结点是指那些已经被确定不能产生问题解的结点。在回溯算法中，当从一个结点出发的所有可能路径都已经被
探索且均未能找到有效的解时，这个结点就成为死结点。简而言之，死结点是没有希望的结点，回溯算法会回退
到这些结点的父结点继续搜索。

总结
所以，当我们谈论回溯法的结点类型时，扩展结点、活结点和死结点都是重要的概念。扩展结点代表当前的工作焦点，
活结点代表仍有潜在可能性的结点，而死结点则表示已经被排除的结点。
理解这些概念对于掌握回溯算法的策略和过程至关重要。

5、回溯法的解题步骤

定义问题的解空间
确定易于搜索的解空间结构：子集树、排列树。
以深度优先方式搜索解空间，搜索过程中用剪枝函数避免无效搜索

常用剪枝函数： a.约束函数在扩展结点处，剪去不满足约束的子树 b.限界函数剪去得不到最优解的子树

6、回溯方式

递归回溯（用递归方法实现回溯）
迭代回溯（采用树的非递归深度优先遍历算法，实现非递归迭代回溯）

7、回溯算法的时间复杂度

8、装载问题的课后习题

9、TSP问题的课后习题答案

10、基本特征的课后习题答案

11、

排序树：n个元素满足某排列，n!个叶子结点。

子集树：满足某种性质的子集，2^n个叶子结点。

12、n皇后问题满足任意两个皇后：

不同行
不同列
不在同一对角线

13、解空间树、排列树、子集树

14、TSP问题和哈密尔顿回路

15、最优解 vs 最优值

16、

排列树：TSP问题，N后问题，批处理作业调度问题

子集树：背包问题，子集和问题、装载问题

17、

约束函数是剪去不含可行解，而限界函数是剪去不含最优解。

线性规划学习笔记

1、线性规划问题的解通常在哪里找到？

A.在可行域的中心
B.在可行域的边界上
C.在可行域的顶点上
D.以上都不是
答案: C
解析: 选项 (3) 在可行域的顶点上。根据线性规划的基本定理，最优解通常在可行域的顶点上。

网络流算法学习笔记

1、网络

2、最大流最小割定理

3、最大流FF(Ford-Fulkerson算法)

4、Edmonds-Karp 算法

Ford-Fulkerson 算法的特例。

5、Dinic算法

6、阻塞流

7、最大流和最小割的值相等。

8、最大流、最小割选择题

9、最大流算法选择题

10、割的容量计算的是流入边，不是流出边。

11、

1、在最大流问题中，哪种算法是用来寻找增广路径的？

A.深度优先搜索 (DFS)
B.广度优先搜索 (BFS)
C.贪心算法
D.动态规划
答案与解析: 选项 (2) 广度优先搜索 (BFS)。
例如，Ford-Fulkerson 方法中使用的 Edmonds-Karp 算法就是利用 BFS 来寻找增广路径。

2、在网络流中，如果一个网络的最大流为 k，则从源点到汇点的最小割的容量是多少？

A.小于 k
B.等于 k
C.大于 k
D.无法确定
答案与解析: 选项 (2) 等于 k。
根据最大流最小割定理，网络的最大流值等于从源点到汇点的最小割的容量。

3、在最大流问题中，每条边的流量必须满足哪两个条件？

A.不超过该边的容量且等于该边的容量
B.不超过该边的容量且为非负值
C.等于该边的容量且为非负值
D.为负值或等于该边的容量
答案与解析: 
选项 (2) 不超过该边的容量且为非负值。流量不能超过边的容量，并且必须是非负值。

填空题
1、在网络流问题中，________ 定义了网络中每个节点除源点和汇点外的流量平衡条件。

答案与解析: 
流量守恒 (Flow Conservation)。在每个中间节点，进入该节点的总流量必须等于离开该节点的总流量。

2、在 Ford-Fulkerson 算法中，如果在残余网络中不存在从源点到汇点的路径，则算法________。

答案与解析:
终止 (Terminates)。Ford-Fulkerson 算法在残余网络中寻找从源点到汇点的增广路径，
如果没有这样的路径存在，算法得出最大流并终止。

算法分析和问题的计算复杂度

NP完全性学习笔记

1、易解与难解

易解问题：有多项式时间算法
难解问题：不存在多项式时间算法

已证明难解的问题：

a.不可计算的问题图灵1936停机问题：输入+程序，是否会停机

b.有算法但至少需要指数或更多时间和空间

既没有多项式时间算法，又未证明是难解的问题

•哈密顿回路货郎背包

2、判定问题与优化问题

判定问题：回答是与否的问题。

k独立集售货员问题（长度不超过D）

优化问题：构造一个解使目标函数最大或最小

最大独立集售货员（最短路）

3、P与NP

P类：所有多项式时间可解的判定问题组成的问题类

EXP类：所有指数时间可解的判定问题组成的问题类

NP：所有多项式时间可验证的判定问题组成的问题类

4、确定型与非确定型

5、P与NP

6、NP-完全

7、NP-完全问题的性质

8、NP完全问题的解题策略

9、典型的NP完全问题：m着色问题、旅行商TSP问题。

10、

期末考试要点

考核时长120分钟。考核结束后可以与老师讨论。

1、填空题（10分，5道题，每道题2分，都是单选）

2、选择题（10分，5道题，每道题2分）

前两部分均是考察基础概念。

3、应用题（3～6题，都是20分1题，一共80分）

题1，第二章的分治

关键词
1、分治过程（初始状态，第1趟状态，第n躺状态）
2、分治的算法分析，分析时间复杂度（数学推理/图示）

题2，第三章的动态规划

关键词
1、找到状态（小明爬楼梯例子），状态表达的变量/属性
2、状态转移方程（核心，初始状态、结束状态、过程中一般的状态）
3、边界情况
4、函数的编写（根据状态转移方程翻译为代码，用c++或者伪代码，将状态转移方程表达出来）

题3，第四章贪心

关键词
1、思路，构造局部最优的策略
2、时间复杂度（关键步骤在哪里）

题4，第五章回溯

关键词
1、解空间，构造是关键
2、两个基本的类型（a.子集树 b.排列树）
注：
1、画出树，解结构的形态
2、求解最优，并解释表达的内涵

4、复习策略：

5道选择和5道填空大部分集中在
- 第1章：基础知识
- 第6章：线性规划
- 第7章：网络流算法
- 第8章：算法分析和问题的计算复杂度
- 第9章：NP完全性
大题的章节，填空选择也可能会涉及。

4道大题集中于
- 第2章分治策略
- 第3章动态规划
- 第4章贪心算法
- 第5章回溯和分支限界

选择题

1、算法必须具备输入、输出和（D）等4个特性。
A. 可行性和安全性
B．确定性和易读性
C. 有穷性和安全性
D. 有穷性和确定性
答案：D
解析：
算法是解决问题的一系列明确的步骤。要成为有效的算法，它必须具备几个关键特性：
输入：算法应有零个或多个输入。
输出：至少有一个输出，即算法的结果。
有穷性：这意味着算法必须在执行有限的步骤后终止。这是非常关键的，
因为如果一个算法永远不会结束，那么它就不能用来有效地解决实际问题。
算法必须保证在经过一定数量的步骤后能够达到结束状态，无论是成功找到答案还是确定无解。
确定性：算法的每一步骤都必须明确无误，不能有歧义。这意味着在相同的输入下，
算法应该产生相同的输出。

2、算法分析中，记号O表示（），记号Ω表示（A）
A.渐近下界
B.渐近上界
C.非渐近上界
D.非渐近下界
答案：B，A
解析：
大O表示法 (Big O Notation) - 表示渐近上界
大O表示法用于描述算法性能的上限。它代表了算法在最坏情况下的运行时间复杂度。
例如, 如果一个算法的时间复杂度为O(n²), 这意味着在最坏情况下，算法的运行
时间是输入大小的平方的函数。
大Ω表示法 (Big Omega Notation) - 表示渐近下界
大Ω表示法用于描述算法性能的下限。它代表了算法在最佳情况下的运行时间复杂度。
例如, 如果一个算法的时间复杂度为Ω(n), 这意味着在最佳情况下，算法的运行时
间至少与输入大小成正比。
这两种表示法帮助我们从两个不同的角度理解算法的性能：
大O描述了算法可能的最慢速度，而大Ω描述了算法可能的最快速度。

题2拓展补充：

1、假设有两个函数 f(n) = n² 和 g(n) = n³，那么 g(n) 与 f(n) 的关系是什么？

答案：f(n) = O(g(n))
解析：

2、如果 h(n) = 3n + 2，j(n) = 5n，则 h(n) 和 j(n) 的关系是什么？
答案：h(n) = Θ(j(n))
解析
这两个函数的主导项都是线性的（即 n），所以它们的增长率相同。
因此，h(n) = Θ(j(n))，表示两者具有相同的渐近增长率。

3、对于函数 k(n) = n² + n 和 m(n) = 2n²，k(n) 是什么关系？

答案
k(n) = Θ(m(n))

解析
尽管 k(n) 包含一个 n² 和一个 n 项，但它的主导项是 n²，这与 m(n) = 2n² 的主导项相同。
因此，这两个函数在增长率上是相似的，即 k(n) 和 m(n) 是同阶的，k(n) = Θ(m(n))。
这意味着在大的输入值时，这两个函数的增长率相似。

补充资料

3、假设某算法在输入规模为 n 时的计算时间为 T(n) = 3*2^n。在某台计算机上实现并完成该算法的时间为 t 秒。现有另一台计算机，其运行速度为第一台的 64 倍，那么在这台新机器上用同一算法在 t 秒内能解输入规模多大的问题？
A. n+8
B. n+6
C. n+7
D. n+5
答案：B
解析：

4、设问题规模为 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(N^2logN)
答案：C
解析：涉及知识点—主定理

应用题

1、求解递推方程

T(n)=9T(n/3)+n

2、求解递推方程

T(n)=T(2n/3)+1

3、求解递推方程

T(n)=3T(n/4)+nlogn

4、求解递推方程

T(n)=2T(n/2)+nlogn

用到递归树求解。

在递归算法的时间复杂度分析中，递归成本通常是不可以忽略的，它对于确定总的时间复杂度至关重要。然而，有时在递归树的分析中，如果非递归部分的成本显著高于递归部分的成本，那么在总的时间复杂度中非递归成本会成为主导项。

答案貌似有问题。

期末复习题1

1、选择题

1.算法必须具备输入、输出和（  ）等 4 个特性。
A．可行性和安全性 B．确定性和易读性
C．有穷性和安全性 D．有穷性和确定性
答案：D
解析：
A选项提到的“可行性和安全性”，虽然重要，但并不是算法的基本特性。
B选项中的“易读性”，指的是代码的可读性和易于理解，这更多是编程实践的一个方面，而非算法本身的基本特性。
C选项同样提到了“安全性”，这并不属于算法的基本特性。
D选项提到了“有穷性和确定性”，这两个都是算法的基本特性。

2.算法分析中，记号 O 表示（ B ），记号Ω表示（ A ）
A.渐进下界 B.渐进上界
C.非紧上界 D.紧渐进界
答案：B、A
解析：
大O记号（O） - 渐进上界:
定义: 大O记号用于描述算法的最坏情况运行时间的上限。当我们说一个算法的时间复杂度是O(f(n))时，
我们的意思是：在最坏的情况下，该算法的运行时间不会超过f(n)的某个常数倍。
例子: 如果一个算法的运行时间是O(n²)，这意味着在最坏的情况下，它的运行时间增长率不会超过输入大小n的平方的某个倍数。
关键点: 这是一种对算法在最坏情况下性能的保守估计。

大Omega记号（Ω） - 渐进下界:
定义: 大Omega记号用于描述算法的最佳情况运行时间的下限。当我们说一个算法的时间复杂度是Ω(g(n))时，
我们的意思是：在最好的情况下，该算法的运行时间至少是g(n)的某个常数倍。
例子: 如果一个算法的运行时间是Ω(n)，这意味着在最好的情况下，它的运行时间增长率至少与输入大小n的某个倍数相同。
关键点: 这是一种对算法在最佳情况下性能的乐观估计。

如果函数f(n)的渐近的上界和下界相等，都是g(n)，则称g(n)是f(n)的渐近的紧的界。或称函数f(n)的阶是g(n)。

3.假设某算法在输入规模为 n 时的计算时间为 T(n)=3*2^n。在某台计算机上实现并
完成该算法的时间为 t 秒。现有另一台计算机，其运行速度为第一台的 64 倍，那
么在这台新机器上用同一算法在 t 秒内能解输入规模为多大的问题？（  ）
A．n+8 B．n+6
C．n+7 D．n+5
答案：B
解析：

4.设 问 题 规 模 为 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(N²logN)
答案：C
解析：

5.直接或间接调用自身的算法称为（ B ）。
A．贪心算法 B．递归算法
C．迭代算法 D．回溯法
答案：B
解析：
题目是关于一个特定类型的算法的定义：直接或间接调用自身的算法。这种算法的定义符合选项B - 递归算法。

递归算法（B）:
定义: 递归算法是一种在其定义中直接或间接调用自身的算法。在递归算法中，问题被分解成更小的、类似的子问题，直到达到一个基本案例，
这个基本案例可以直接解决而不需要进一步递归。
例子: 一个典型的例子是计算斐波那契数列或阶乘。
其他选项:
A. 贪心算法：它是一种在每一步选择当前最好的解决方案的算法，不回头考虑之前的选择。这种方法并不包含直接或间接调用自身的特性。
C. 迭代算法：迭代算法通过重复执行一系列操作来解决问题，但这些操作不包括调用算法本身。
D. 回溯法：虽然回溯法经常使用递归来实现，但它是一种特定的算法，用于在解决问题的过程中穷举所有可能的解决方案，并“回溯”以找到最优解。

6.Fibonacci 数列中，第 4 个和第 11 个数分别是（  ）。
A．5，89 B．3，89
C．5，144 D．3，144
答案：B
解析：
1 1 2 3 5 8 13 21 34 55 89。
注：标准斐波那契数列的前两个数字是1和1。

8.一个问题可用动态规划算法或贪心算法求解的关键特征是问题的（  ）。
A．重叠子问题 B．最优子结构性质
C．贪心选择性质 D．定义最优解
答案：B
解析：
重叠子问题（A）:
这是动态规划算法的一个关键特征。在动态规划中，问题被分解成子问题，这些子问题被多次解决。
动态规划通过存储这些子问题的解决方案来优化计算，避免重复工作。然而，这并非贪心算法的特征。

最优子结构性质（B）:
这是动态规划和贪心算法共有的关键特征。如果一个问题具有最优子结构性质，那么问题的最优解
可以通过其子问题的最优解来构造。在动态规划中，我们利用这个性质来构建整体解决方案。
在贪心算法中，我们假设通过局部最优选择（每一步都做出当前看来最好的选择）可以达到全局最优解。

贪心选择性质（C）:
这是贪心算法的特征，其中局部最优选择被假设为会导致全局最优解。然而，这并不是动态规划所特有的，
因为动态规划不依赖于单一的“贪心”选择；相反，它考虑了多种选择的可能性。

定义最优解（D）:
定义最优解是解决任何优化问题的基本步骤，不特定于动态规划或贪心算法。
综上所述，最适合作为动态规划和贪心算法共有的关键特征的是最优子结构性质（B）。
这表明这两种算法都依赖于通过组合子问题的最优解来构造整体问题的最优解。因此，答案是 B. 最优子结构性质。

9.下列哪个问题不用贪心法求解（  ）。
A．哈夫曼编码问题 B．单源最短路径问题
C．最大团问题 D．最小生成树问题
答案：C
解析：
哈夫曼编码问题 (A): 这是一个经典的使用贪心策略的问题。在构建哈夫曼树时，总是选择频率最低的两个节点合并。
这是一个典型的贪心选择。

单源最短路径问题 (B): 特别是当我们考虑到Dijkstra算法时，这个问题可以通过贪心法解决。在每一步中，
算法都会选择当前最短的路径扩展到未访问的节点。

最大团问题 (C): 这个问题通常不使用贪心策略来解决。最大团问题是一个NP完全问题，意味着没有已知的多
项式时间算法（包括贪心算法）能解决所有情况。通常需要使用回溯、分支界限或者近似算法。书本P127，回溯和分支限界中提及。

最小生成树问题 (D): 这个问题可以通过贪心算法解决，如Kruskal算法或Prim算法。
这些算法在每一步都选择最小权重的边，以构建最小生成树。

10.下列算法中通常以自底向上的方式求解最优解的是（  ）。
A．备忘录法 B．动态规划法
C．贪心法 D．回溯法
答案：B
解析：
备忘录法 (A): 这通常与动态规划相关，但它更多地采用自顶向下的方法。在备忘录法中，原问题被分解成更小的子问题，
并且结果被存储（或“记忆化”），以避免重复计算。尽管它涉及到子问题的解决，但这种方法的执行顺序是从顶部问题开始，
逐渐深入到子问题。

动态规划法 (B): 动态规划是一种解决复杂问题的方法，通过将问题分解成更简单的子问题，并构建这些子问题的解决方案，
从而解决整个问题。动态规划可以采用自底向上或自顶向下的方法，但在经典的动态规划实践中，自底向上的方法更为常见。
在这种方法中，我们首先解决最小的子问题，并逐步构建更大的问题的解决方案。

贪心法 (C): 贪心算法在每一步都做出当下看起来最好的选择，以期望这会导致全局最优解。这种方法通常不是自底向上的；
相反，它从某个初始解出发，通过局部最优的选择来扩展这个解。

回溯法 (D): 回溯法是一种解决问题的算法，通过尝试分步的方法逐步找到问题的解决方法。当它遇到一个问题没有解决方
案的情况时，它会回退一步尝试其他可能的解决方案。这更像是一种自顶向下的探索方法，而不是自底向上。

综上所述，答案是 B. 动态规划法。动态规划法在求解最优解时，通常采用自底向上的方法，首先解决最小的子问题，
然后逐步向上构建，直到解决原始问题。

11.下列算法中不能解决 0/1 背包问题的是（  ）。
A．贪心法 B．动态规划
C．回溯法 D．分支限界法
答案：A
解析：
贪心法 (A): 贪心算法在每一步都做出在当前看来最优的选择。在 0/1 背包问题中，贪心算法可能会根据价值
或价值密度（价值除以重量）来选择物品。然而，这种方法不能保证总是得到最优解，因为它可能错过了更优的
组合，这些组合可能在初看时并不是最优的。因此，贪心法并不总是适用于解决 0/1 背包问题。

动态规划 (B): 动态规划是解决 0/1 背包问题的经典方法。它通过构建一个解决子问题的表格，并从最简单的
子问题开始，逐步解决更复杂的问题，最终找到最优解。

回溯法 (C): 回溯法是一种通过遍历所有可能情况来找到问题所有解的算法。对于 0/1 背包问题，回溯法可以
通过尝试包括或不包括每个物品来找到所有可能的组合，从而找到最优解。

分支限界法 (D): 分支限界法是一种用于解决优化问题和计数问题的方法，它系统地遍历候选解的树形结构。
在 0/1 背包问题中，它可以有效地剪枝，从而只搜索有希望的分支，也能找到最优解。
因此，答案是 A. 贪心法，因为它不能保证总是解决 0/1 背包问题。贪心法可能会提供一个解，但这个解不一定是最优的。

12.下列哪个问题可以用贪心算法求解（ ）。
A．LCS 问题 B．批处理作业问题
C．0-1 背包问题 D．哈夫曼编码问题
答案：D
解析：
LCS 问题 (A): LCS (最长公共子序列，Longest Common Subsequence)问题是寻找两个序列共有的最长子序列的问题。
这个问题不能用贪心算法有效解决，因为贪心选择可能导致错过更长的公共子序列。通常使用动态规划来解决。

批处理作业问题 (B): 这个问题通常指的是在计算机科学中的作业调度问题，需要考虑作业的顺序以优化总体性能。
这个问题的解决方案通常不是贪心的，因为局部最优选择可能不会导致全局最优。

0-1 背包问题 (C): 正如前面提到的，0-1 背包问题不能用贪心算法有效解决，因为贪心选择可能导致非最优解。

哈夫曼编码问题 (D): 这是一个通过构建最优前缀编码树来最小化编码总长度的问题。哈夫曼算法是一个贪心算法的经典例子，
它在每一步选择最低频率的两个节点合并，这种贪心选择可以保证找到最优的前缀编码。

因此，答案是 D. 哈夫曼编码问题。这个问题可以用贪心算法求解，因为在每一步合并频率最低的两个节点这一贪心策略可以
保证最终得到最优的前缀编码

13.用回溯法求解最优装载问题时，若待选物品为 m 种，则该问题的解空间树的结点
个数为（ ）。 
A．m!  B．2^(m+1)
C．2^(m+1)-1  D．2^m
答案：C
解析：
最优装载问题是一个典型的组合优化问题，可以通过回溯法来求解。在这个问题中，
我们需要决定哪些物品被装载以优化某个特定的目标（例如最大化价值或最小化重量）。

在用回溯法解决这类问题时，我们通常构建一个解空间树，其中每个节点代表一个决策
（装载或不装载某个物品）。对于 m 种待选物品，解空间树的每个层级代表对一个物
品的决策，每个物品有两种选择：装载或不装载。

A. m!: 这代表 m 种物品的所有排列，但在最优装载问题中，物品的排列顺序并不重要，重要的是哪些物品被选中。
因此，m! 不是解空间树节点数的正确表达。

B. 2^(m+1) 和 C. 2^(m+1)-1: 这两个选项都是基于二叉树的节点数计算的。在一个完全二叉树中，
如果树的高度为 h，那么它的节点总数是 2^h - 1（这是选项 C）。如果树的最后一层完全满了，那么节点总数
是 2^(h+1) - 1，这里 h = m，所以选项 C 是正确的。

D. 2^m: 这代表每个物品两种选择（装载或不装载）的所有可能组合。在一个有 m 个物品的问题中，
会有 2^m 种组合，但这只计算了树的叶子节点，没有包括决策树中的非叶子节点。

综上所述，答案是 C. 2^(m+1)-1。这是因为每个物品有两种选择（即二叉树），所以对于 m 种物品，
解空间树是一个高度为 m 的完全二叉树，其总节点数为 2^(m+1)-1。

14.二分搜索算法是利用（  ）实现的算法。
A．分治策略 B．动态规划法
C．贪心法 D．回溯法
答案：A
解析：
分治策略（A）：在二分搜索中，我们将问题分解为更小的子问题。具体来说，我们将数组分为两部分，
并确定所寻找的元素是在左侧还是右侧。通过这种方式，我们每次都将搜索范围减少一半，直到找到
目标元素或者确定元素不存在。这是分治法的一个典型应用，因为我们在每一步都将问题划分为两个更小的部分。

动态规划法（B）：与二分搜索不同，动态规划是解决具有重叠子问题和最优子结构的问题的方法。
它通常用于求解具有递推关系的问题，通过存储子问题的解来避免重复计算。二分搜索并不涉及重叠子问题或最优子结构的概念。

贪心法（C）：贪心算法在每一步都采取当前看起来最优的选择，而不考虑整体的最优解。二分搜索不是
在每一步都寻找局部最优解，而是通过比较和切分来系统地缩小搜索范围。

回溯法（D）：回溯算法是一种通过试错来寻找所有/某些解决方案的算法，当它通过尝试可能的分支找
到一个可能的解决方案时会回溯。二分搜索并不涉及试错或回溯；它是一种直接且系统的搜索方法。

因此，最适合描述二分搜索算法的是A. 分治策略。二分搜索通过不断地将问题分解为更小的部分，
并在每一步中减少搜索范围，直到找到答案或确定答案不存在。主人，这是二分搜索算法的基本解析。

15.下列不是动态规划算法基本步骤的是（  ）。
A．找出最优解的性质 B．构造最优解
C．算出最优解(应该是最优值) D．定义最优解
答案：A
解析：
要确定哪一个选项不是动态规划算法的基本步骤，我们需要回顾动态规划算法的关键特征和步骤：

定义子问题（D）：在动态规划中，首先需要定义子问题。这是基本步骤之一，
因为动态规划算法依赖于解决重叠的子问题并使用这些解来构建整体问题的解。

计算子问题的最优解（C）：这一步是动态规划中的核心。算法需要计算每个子问题的最优解，
并通常将这些解存储在一个表格中以避免重复计算。

构造最优解（B）：一旦所有子问题的最优解都被找到，动态规划算法会从这些子问题的解中
构建出整个问题的最优解。这个步骤对于完成整个算法过程至关重要。

找出最优解的性质（A）：这一步骤通常是指在解决问题之前理解问题的性质，例如最优子结构
和重叠子问题。虽然这对于设计一个有效的动态规划算法很重要，但它并不是动态规划算法本身的“步骤”，
而是解决问题之前的一个准备步骤。

综上所述，如果我们严格区分算法设计的准备工作和算法本身的执行步骤，那么可以认为“A. 找出最优解的性质”
并不直接属于动态规划算法的执行步骤，而是一个前期的准备或理论分析步骤。
因此，在这个上下文中，选项A可以被视为“不是动态规划算法基本步骤”的选项。

16.下面问题（  ）不能使用贪心法解决。
A．单源最短路径问题 B．N 皇后问题
C．最小花费生成树问题 D．哈夫曼编码问题
答案：B
解析：
在这个问题中，我们需要识别哪个问题不能使用贪心法解决。贪心算法是一种在每一步选择中都选取当前状态下最好的选择，
而不考虑以后可能产生的后果。这种方法对于某些问题来说是有效的，但对于其他问题则可能无法找到最优解。
让我们逐一分析这些选项：

单源最短路径问题（A）：对于没有负权边的图，贪心算法是有效的。例如，Dijkstra算法就是一个使用
贪心策略来寻找单源最短路径的算法。

N皇后问题（B）：这个问题要求在N×N的棋盘上放置N个皇后，使得它们互不攻击。这是一个典型的回溯
问题，因为你需要考虑所有皇后的放置方式来找到解决方案。贪心算法在这里不适用，因为在放置每个
皇后时，对当前棋盘最优的选择可能导致无法放置后续的皇后。

最小花费生成树问题（C）：这个问题可以使用贪心算法解决。最著名的例子是Kruskal算法和Prim算法，
它们都是使用贪心策略来找到最小生成树的。

哈夫曼编码问题（D）：这是一种压缩数据的方法，也是贪心算法的一个应用。在哈夫曼编码中，经常出现的
字符使用较短的编码，不常出现的字符使用较长的编码，这是一种典型的贪心选择方法。

综上所述，贪心法可以有效解决单源最短路径问题、最小花费生成树问题和哈夫曼编码问题。然而，对于N皇后
问题，贪心法由于其局限性（即在每一步都做局部最优选择）无法保证找到全局最优解。
因此，不能使用贪心法解决的问题是 B. N皇后问题。

17.用二分搜索算法在 n 个有序元素表中搜索一个特定元素，在最好情况和最坏情况
下搜索的时间复杂性分别为（  ）。
A．O(1)，O(logn)  B．O(n)，O(logn) 
C．O(1)，O(nlogn)  D．O(n)，O(nlogn)
答案：A
解析：
二分搜索算法是一种在有序元素表中查找特定元素的高效方法。这个算法的核心思想是将搜索区间分成两半，
然后根据目标元素与中间元素的比较结果来确定接下来搜索的区间。现在，让我们来探讨这个算法在最好
情况和最坏情况下的时间复杂度。

最好情况：在最好的情况下，我们要找的元素恰好是中间元素，也就是说，在第一次尝试时我们就找到了目标。
在这种情况下，时间复杂度是 O(1)，因为我们只进行了一次操作。

最坏情况：在最坏的情况下，每次比较都不会直接找到目标元素，我们需要不断地将搜索区间分成两半。
由于每次操作都将搜索区间减半，所以二分搜索的时间复杂度是 O(logn)。这意味着随着元素数量的增加，
所需的步骤数增加的速度是对数的。
所以，基于这些分析，我们可以看到选项 A（O(1)，O(logn)）是正确的答案。这个选项正确地描述了
二分搜索在最好情况下（即第一次就找到目标元素）和最坏情况下（即每次都需要将搜索区间分成两半
直到找到目标元素）的时间复杂度。

21.下列关于计算机算法的描述不正确的是（  ）。
A．算法是指解决问题的一种方法或一个过程
B．算法是若干指令的有穷序列
C. 算法必须要有输入和输出
D．算法是编程的思想
答案：C
解析：
A. 算法是指解决问题的一种方法或一个过程：这个描述是正确的。算法确实是一组定义清晰的指令集合，
用于解决特定的问题或执行特定的任务。

B. 算法是若干指令的有穷序列：这也是正确的。算法由一系列步骤组成，这些步骤有明确的开始和结束，
这意味着它们是有限的。

C. 算法必须要有输入和输出：这个描述是有争议的。大多数算法确实涉及输入和产生输出，但并非所有
算法都严格要求有输入。例如，某些算法可能只生成一系列数据（只有输出，没有输入），或者仅基于内
部状态执行操作（既无输入也无输出）。因此，这个描述可能被视为不完全正确。

D. 算法是编程的思想：这个说法是比较宽泛的。算法更准确地说，是解决问题的方法或步骤。它确实是编
程中一个重要的组成部分，但将算法仅描述为“编程的思想”可能过于简化了其定义和重要性。

根据上述分析，最可能被认为不正确的描述是 C. 算法必须要有输入和输出。虽然大多数算法确实涉及
输入和输出，但这并非算法的绝对要求。因此，C 选项是这个问题的答案。

24.分治法所能解决的问题应具有的关键特征是（）
A．该问题的规模缩小到一定的程度就可以容易地解决
B．该问题可以分解为若干个规模较小的相同问题
C．利用该问题分解出的子问题的解可以合并为该问题的解
D．该问题所分解出的各个子问题是相互独立的
答案：C
解析：
分治法是一种重要的算法设计策略，主要用于解决复杂问题。这种方法的核心是将大问题分解成若干个小问题，
单独解决这些小问题，然后将解决方案合并以解决原来的大问题。我们来逐一分析给出的选项：

A. 该问题的规模缩小到一定的程度就可以容易地解决：这个描述是分治法的一个特征，但它不是分治法的关键特征。
小规模问题更容易解决是许多算法共有的特性，并非分治法特有。
B. 该问题可以分解为若干个规模较小的相同问题：这是分治法的一个重要特征。将大问题分解为多个小问题是分治
法的核心步骤之一。
C. 利用该问题分解出的子问题的解可以合并为该问题的解：这是分治法的关键特征。分治法的核心不仅在于分解问题，
还在于能够将子问题的解有效地合并成原问题的解。
D. 该问题所分解出的各个子问题是相互独立的：这也是分治法的一个重要特征，因为它使得子问题可以独立解决，
甚至可以并行处理。
虽然所有这些选项都描述了分治法的某些特征，但关键在于如何将子问题的解合并成原问题的解。因此，选项 C 
是最准确的答案。在分治法中，能否将子问题的解有效组合成原问题的解是整个策略成功与否的关键。

分治算法大题

0、考察重点
题1，第二章的分治

关键词
1、分治过程（初始状态，第1趟状态，第n躺状态）
2、分治的算法分析，分析时间复杂度（数学推理/图示）

注：
分析时间复杂度的两种方法：
- 数学推理：迭代法、换元迭代、主定理
- 图示：递归树

注：该题可忽略，题目场景不常规。归并排序的分治思想需好好掌握。可见题9归并排序分治常规题。
1、假设你是一名软件工程师，正在开发一款应用，该应用需要处理和排序大量的用户数据。
这些数据是以一个“山脉数组”的形式给出的。山脉数组是一个先递增后递减的数组，
例如 [1, 3, 5, 7, 6, 4, 2]。你的任务是使用分治算法，先找到数组中的最大值（山顶），
然后对数组的两部分（山脉的两侧）分别进行合并排序。
a.描述找到山脉数组中最大值的分治过程，包括初始状态，第1趟状态，和第n趟状态。
b.描述对山脉数组两侧进行合并排序的分治过程。
c.分析整个算法（包括查找最大值和排序两侧）的时间复杂度。

考察知识点：二分查找、归并排序

解答：
a.分治过程

初始状态：
给定一个山脉数组，例如［1,3,5,7,6,4,2］，其中数组先递增后递减。

第1趟状态
•使用二分查找法来找到最大值。
•首先，找到数组的中间元素（例如，7）。
•然后，比较中间元素与其相邻的元素，以判断最大值是在左侧递增部分还是右侧递减部分。

第n趟状态
•重复上述过程，每次都将搜索范围缩小一半，直到找到最大值。

b.对山脉数组两侧进行合并排序的分治过程。
左侧数组（递增部分）
1.分解：将数组分成两个子数组。
2.解决：递归地对这两个子数组进行归并排序。
3.合并：合并两个已排序的子数组。
右侧数组（递減部分）
1. 分解：同样将数组分成两个子数组。
2. 解决：递归地对这两个子数组进行归并排序。
3. 合并：合并两个已排序的子数组，但由于原始数组是递减的，需要在合并时逆序放置元素。

c.时间复杂度
查找最大值的时间复杂度
•由于使用二分查找，时间复杂度为O（logn），其中、n是数组的长度。
对两侧数组进行排序的时间复杂度
•归并排序的时间复杂度为O（nlogn）。
•由于山脉数组被分为两部分，每部分的排序也是O（nlogn）。
•但由于这两部分排序是连续的而不是并行的，
总的时间复杂度仍然是O（nlogn）。
•注意，虽然我们进行了两次归并排序（数组的两侧），
但它们是对原始数组的不同部分进行的，因此总体的排序步骤并没有增加。

2、
(1)若待排序元素存放于l数组中，且Swap(i,j)函数的作用为交换下标为i和j的两个元素l[i]和l[j]的值。
请写出快速排序算法的C语言程序，包含以下两个函数：
int Partition(int left, int right)
void QuickSort(int left, int right)
(2)对初始数据（5，8，4，6，3，7，1）执行快速排序，每次都选择左边第一个元素作为主元，
请给出每一趟分划操作的结果。并用[]标识子序列的边界。
(3)若待排序数据的规模为n，快速排序算法最好、最坏情况什么时候发生？ 

考察知识点：快速排序

解答：
(1)

int Partition(int left, int right)
{
    int pivot = l[left]; // 选择最左侧的元素作为基准
    int i = left;        // 从left开始，而不是left-1

    for (int j = left + 1; j <= right; j++)
    {
        if (l[j] < pivot)
        {
            i++;
            Swap(i, j);
        }
    }
    Swap(i, left);      // 将pivot放到它的最终位置
    return i;           // 返回pivot的位置
}


// 快速排序（重载函数）
void QuickSort(int left, int right)
{
    if (left < right)
    {
        int pi = Partition(left, right);
        QuickSort(left, pi - 1);
        QuickSort(pi + 1, right);
    }
}

(2)

第一趟结果：[1,4,3],5,[8,7,6]
第二趟结果：[1],[4,3],5,[7,6],[8]
第三趟结果：[1],[3,4],5,[6,7],[8]

(3)
快速排序算法在最好、平均情况下的时间复杂度为O(nlogn)，在最坏情况下的时间复杂度是O(n^2)。
每次分划操作后，若左、右两个子序列的长度基本相等，则快速排序效率最高，为最好情况。
原始序列正向有序或反向有序时，每次划分操作所产生的两个子序列，
其中之一为空序列，则快速排序效率最低，为最坏情况。
时间复杂度数学推导：

3、题目： 使用分治法的 maxmin 算法寻找数组中的最大值和最小值
实例数组： A=(48,12,61,3,5,19,32,7)

要求：
a.分治过程描述： 
描述 maxmin 算法在给定数组 A 上的执行过程。包括初始状态，第1趟状态，直到第n趟（最终）状态。
b.算法分析：
描述分治法的基本原理。分析 maxmin 算法的时间复杂度，包括数学推理和图示说明。

考察知识点：选择问题，选最大与最小

解答：
a. 
初始状态：
数组 A=｛48,12,61,3,5,19,32,7｝

第一趟状态：
分割数组为两部分：｛48,12,61,3｝ 和｛5,19,32,7｝

第二趟状态：
进一步分割每个子数组：
• ｛48,12｝和｛61,3｝
• ｛5, 19｝和｛32,7｝

第三趟状态：
处理每个分割后的子数组：
•在｛48,12｝ 中，48是最大值，12是最小值。
•在｛61,3｝中，61是最大值，3是最小值。
•在｛5,19｝中，19是最大值，5是最小值。
•在｛32,7｝中，32是最大值，7是最小值。

第四趟状态（合并结果）：
将子数组的结果合并以找出整体的最大值和最小值：
•比较｛48,12｝的结果和｛61,3｝的结果得到全局最大值61，最小值3。
•比较｛5,19｝的结果和｛32,7｝的结果得到全局最大值32
（这里需要与之前的最大值61比较），最小值5（需要与之前的最小值3比较）。
最终状态：
综合上述结果，最大值为61，最小值为3。

b.
基本原理：
分治法是一种递归算法，它将一个大问题分解为两个或更多的相似的小问题，
这些小问题互相独立且与原问题形式相同。
解决所有小问题后，再将这些小问题的解决结果合并，以产生原问题的解。

maxmin算法的时间复杂度分析：
•每一次递归，都将问题规模减半，即对半分数组。
•对于每一层递归，我们都进行两次递归调用，每次调用处理数组的一半。
•因此，递归的深度为log2（n），其中n是数组的大小。
•在每一层递归中，我们都进行了常数次的比较操作。

设 T（n）是算法的时间复杂度，则有递推公式：
T(n) = 2T(n/2) + 2

根据主定理，可以解得T（n）=O（n）。

补充：
分治算法的时间复杂度分析：

a（分割因子）：这代表在分治算法中每一步递归中产生的子问题的数量。
例如，在二分查找中，我们每次都将问题分成两部分（a=2），而在归并排序中，
每次递归通常也会产生两个子问题（a=2）。

n/b（子问题大小）：这里的n是原始问题的大小，而b是一个用于划分每个子问
题的大小的因子。在每一步递归中，原始问题被分割成更小的子问题，
每个子问题的大小大约是原始问题大小的1/b。
例如，在归并排序中，如果我们有n个元素，每个子问题将包含n/2个元素（b=2）。

f（n）（合并成本或额外工作）：这表示在分治算法的每个递归步骤中，除了递归
地解决子问题外，还需要进行的额外工作。这可能涉及合并子问题的解决方案，
或者对子问题的结果进行某种形式的处理。
例如，在归并排序中，f（m）代表合并两个已排序的子数组所需的时间，这通常与n成正比。

4、题目： 在电子图书馆的有序书籍目录中应用二分查找
背景场景： 你是一名图书管理员，在电子图书馆管理系统中有一个按书籍编号顺序排列的有序列表。
这个列表包含以下编号：{1，3，9，12，32，41，45，62，75，77，82，95，100}。
你需要快速找到编号为82的书籍。

任务：
1、分治过程描述：
描述使用二分查找法在有序列表中查找编号为82的书籍的过程。
包括初始状态，第1趟状态，直到查找成功（第n趟）的状态。
2、算法分析：
解释二分查找法如何分解问题并逐步缩小查找范围。
分析二分查找的时间复杂度，包括数学推理和图示说明。
要求：计算在查找过程中进行了多少次比较，并描述每一次比较的具体过程。

考察知识点：二分查找

解答：
1.分治过程
初始状态
• 数组：{1，3，9，12，32，41，45，62，75，77，82，95，100}
• 查找范围：整个数组
• low =0, high = 12（数组索引）

第1趟
• 中间索引：mid =（0+12）/2=6（对应编号45）
• 比较：45<82
• 更新查找范围：右半部分，low=mid+1=7

第2趟
• 中间索引：mid =（7+12）/2=9（对应编号77）
• 比较：77<82
• 更新查找范围：右半部分，low=mid+1=10

第3趟
• 中间索引：mid =（10+12）/2=11（对应编号95）
• 比较：95>82
• 更新查找范围：左半部分，high=mid-1=10

第4趟（查找成功）
• 中间索引：mid =（10+10）/2=10（对应编号82）
• 比较：82==82
• 查找成功：找到编号82的书籍

2.算法分析
如何分解问题
•二分查找通过比较中间元素与目标值来分解问题。
•如果中间元素不是目标值，算法排除一半的元素，只在剩下的一半继续查找。
•这个过程不断重复，每次都将查找范围减半，直到找到目标值或查找范围为空。

时间复杂度分析
•每次比较都将查找范围减半。
•在最坏情况下，算法需要进行log2n次比较，其中n是数组的大小。
•因此，二分查找的时间复杂度是O（logn）。

比较次数
•在本例中，进行了4次比较来找到编号为82的书籍。
•比较的具体过程见第1小问。

图示说明
•每一趟查找都可以视为一次在二叉树的层级上的遍历。
•树的高度决定了最大比较次数，即log2n。

5、考虑一个具体的整数数组，例如：8,3,5,7,6,2,9,1。您的任务是应用分治策略来找出这个数组中的最大元素。

问题要求：
1. 描述分治过程：详细描述上述分治过程中的每一步，包括如何分割和合并子段。
2. 算法分析：分析此分治算法的时间复杂度。使用数学推理或图示方法来说明你的分析。
考虑每个阶段的比较次数，以及总共需要的分割合并次数。

考察知识点：选择问题，选最大

解答：
1.
分解：
首先，将数组分成两个部分。例如，我们可以在中间分割，得到两个子数组：［8,3,5,7］和［6,2,9,1]。

解决：
递归地对每个子数组应用相同的分治策略。
•对于［8,3,5,7］，继续分割为［8,3］和［5,7]，然后再分别分割，直到每个子数组只有一个元素。
•对于［6,2,9,1]，执行相同的分割过程。

合并：
在每个分割级别上，比较子数组的元素，选择最大的元素，然后向上合并。
•比如，在最底层，我们比较单个元素，然后在上一层比较［8］和［3］得到8，比较［5］和［7］得到7，
以此类推，最终得到整个数组的最大元素。

2.
时间复杂度的分析通常基于算法的基本操作次数。
该分治算法的时间复杂度是O（n）。
分析：

6、考虑一个具体的整数数组，例如：8,3,5,7,6,2,9,1。您的任务是应用分治策略来找出这个数组中的第二大元素。

问题要求：
1. 描述分治过程：详细描述上述分治过程中的每一步，包括如何分割和合并子段。
2. 算法分析：分析此分治算法的时间复杂度。使用数学推理或图示方法来说明你的分析。
考虑每个阶段的比较次数，以及总共需要的分割合并次数。

考察知识点：选择问题，选第二大

解答：
1.
分解:
•将数组分成两个部分，例如，数组［8,3,5,7,6,2,9,11]在中间分割成两个子数组
［8,3,5,7］和［6,2,9,1]。
解决：
•递归地对每个子数组应用相同的分治策略，同时寻找子数组中的最大值和第二大值。
合井：
•在每个递归步骤中，比较来自两个子数组的最大值和第二大值，从而确定当前递归层
的最大值和第二大值。

2.
分治过程
•这个函数使用了分治策略。对于一个包含n个元素的数组，每次递归都将问题分成两个子问题，
每个子问题处理一半的元素。
•每一层递归都需要对每个子区间进行比较操作，以确定这个区间的最大值和第二大值。
•因此，分治过程中，每个元素会参与log（n）次比较（因为每次都是将问题规模減半）。

时间复杂度计算
分析：

7、斐波那契数列定义为 F（O）=0, F（1）=1，对于n>1, F（n）= F（n-1）+F（n-2）。
你的任务是编写一个程序，使用分治算法来计算斐波那契数列的第n项，并分析算法的时间复杂度。

1.描述算法的分治过程。
•指出算法的初始状态。
•描述第1趟的状态。
•描述第n趟的状态。
2.编写分治算法。
•描述算法的基本情况。
•描述算法如何递归地分解问题。
3.分析算法的时间复杂度。
•使用数学推理或图示来说明时间复杂度。
•解释为什么时间复杂度是这样的。

考察知识点：斐波那契数列

解答：
1. 描述算法的分治过程。
算法的初始状态
•初始状态是计算斐波那契数列的第n项，其中F（0）=0和F（1）= 1。

第1趟的状态
•在第1趟，如果n大于1，算法将问题分解为计算F（n-1）和F（n-2）。

第n趟的状态
•在第n趟，算法继续分解问题，直到达到基本情况：计算F（O）或F（1）。

2. 编写分治算法。

基本情况
•当n为0时，返回O；当n为1时，返回1。
递归地分解问题
•对于n>1，递归地计算F（n-1）和F（n-2），然后将它们相加以得到F（n）。

代码实现:

#include <stdio.h>

long long fibonacci(int n) {
    if (n == 0) return 0;
    if (n == 1) return 1;
    return fibonacci(n - 1) + fibonacci(n - 2);
}

int main() {
    int n;
    printf("请输入要计算的斐波那契数列项数：");
    scanf("%d", &n);

    long long result = fibonacci(n);
    printf("斐波那契数列的第%d项是：%lld\n", n, result);

    return 0;
}

3.分析算法的时间复杂度。

数学推理
•斐波那契数列的分治算法对于每个n>1，都进行了两次递归调用。
•这导致递归树的每个节点都分裂成两个子节点，形成一个二叉树的结构。

图示
•可以用一棵二叉树来表示这种递归，其中每个节点有两个子节点（除了叶子节点）。
树的深度为n。

时间复杂度解释
•在这种情况下，时间复杂度可以近似为二叉树的节点总数，即O（2^n）。
•这是因为每增加一个n，递归树的大小几乎翻倍。

总结
•因此，该分治算法的时间复杂度是指数级的，即O（2^n）。这是一个效率非常低的算法，特别是对于较大的n值。

8、假设有三根柱子 A、B和C。开始时，A柱子上有n个逐渐增大的盘子，目标是将这些盘子全部移动到C柱子上，
遵循以下规则：每次只能移动一个盘子，且在移动过程中，大盘子不能放在小盘子上面。
小问分解：
1. 问题一：描述初始状态下，盘子的排列和目标。
2. 问题二：描述第一次移动后，三根柱子上盘子的状态。
3. 问题三：若n=3，详细描述整个移动过程的每一步。
4. 问题四：使用分治策略描述算法的步骤。
5. 问题五：分析此算法的时间复杂度，并解释为什么时间复杂度是这样的。

考察知识点：汉诺塔问题

问题一：初始状态和目标
初始状态
•开始时，所有盘子按照大小顺序排列在A柱上，最大的盘子在底部，最小的盘子在顶部。
目标
•将所有盘子移动到C柱上，移动过程中必须遵循同样的规则：任何时候大盘子不能放在小盘子上面。

问题二：第一次移动后的状态
•第一次移动通常是将最小的盘子（顶部的盘子）从A柱移动到C柱（如果盘子总数是奇数）
或B柱（如果盘子总数是偶数）。
•因此，此时A柱上会有剩下的盘子，B柱或C柱上会有一个最小的盘子。

问题三：n=3的移动过程
1.将最小的盘子从A移到C。
2.将次小的盘子从A移到B。
3.将最小的盘子从C移到B。
4.将最大的盘子从A移到C。
5.将最小的盘子从B移到A。
6.将次小的盘子从B移到C。
7.将最小的盘子从A移到C。

问题四：分治策略描述
分治策略涉及将问题分解为更小的、更易于管理的问题，然后将这些问题的解决方案合并以解決原始问题。
1.分解：将问题分解为移动最上面的n-1个盘子到辅助柱（B柱），然后移动最底部的大盘子到目标柱（C柱）。
2.解决：递归地移动这n-1个盘子。
3.合并：将n-1个盘子从辅助柱移动到目标柱（C柱），在此过程中，初始柱（A柱）作为辅助柱。

问题五：时间复杂度分析
•移动n个盘子的步骤数是指数性增长的。每增加一个盘子，所需的步骤数都会翻倍并加一。
•对于n个盘子，总步骤数 T（n）=2*T（n-1）+1。
•因此，算法的时间复杂度是0（2^n）。

9、归并排序

请用分治策略设计递归的归并排序算法，并分析其时间复杂性（要求：分别
给出 divide、conquer、combine 这三个阶段所花的时间，并在此基础上列出递归
方程，最后用套用公式法求出其解的渐进阶）

解答：
a.三个阶段所花的时间：
1. Divide（分）：将数组分成两个子数组，每个子数组大约是原数组的一半大小。
这个步骤的时间复杂度是 O（1），因为它只涉及计算中点。
2. Conquer（治）：递归地对这两个子数组进行归并排序。当子数组大小减少到1或0时，递归结束。
由于每次递归都会将数组分成一半，所以总共会有logn层递归。
3. Combine（合）：将两个已排序的子数组合并成一个有序的数组。
合并两个大小为n/2的数组的时间复杂度是O（n）。

递归方程为：
T (n) = 2T (n/2) + O(n)
设T（n）是对大小为n的数组进行归并排序所需的时间。那么根据上述分析，递归方
这里，2T（n/2）是两次递归调用处理两个子数组的时间，O（n）是合并时间。

时间复杂性分析：

这表明归并排序在所有情况下的时间复杂度都是 O（nlogn）。

10、

解答：
(1)
基本思路是将数组分成两部分，递归地在每部分中找到最小元素和第二小元素，
然后将这两部分的结果合并以得到整个数组的最小元素和第二小元素。
•分解：将数组 A［1...n］分为两个大小相等的子数组 A［1...n/2］和 A［n/2+1...n］。
•递归求解：分别在这两个子数组中递归地找到最小元素和第二小元素。
这将给我们两对元素（每对包含一个最小元素和一个第二小元素）。
•合并：比较这两对元素，找到整个数组的最小元素和第二小元素。
合并步骤的关键在于，我们首先比较两个最小元素以确定整个数组的最小元素。
然后，我们只需要比较三个元素来确定第二小元素：两个子数组中的第二小元素和较大的最小元素。
(2)
递归方程：
对于大小为n的数组，比较次数 T（n）可以表达为：
T(n) = 2T (n/2) + 3
其中，2T（n/2）是在两个子数组上找到最小元素和第二小元素的比较次数，
3是在合并步骤中确定整个数组的最小元素和第二小元素的额外比较次数。

证明略。

动态规划大题

0、考察重点
题2，第三章的动态规划

关键词
1、找到状态（小明爬楼梯例子），状态表达的变量/属性
2、状态转移方程（核心，初始状态、结束状态、过程中一般的状态）
3、边界情况
4、函数的编写（根据状态转移方程翻译为代码，用c++或者伪代码，将状态转移方程表达出来）

1、使用动态规划策略求解最长公共子序列问题
在这个问题中，我们的目标是利用动态规划策略来找出两个序列之间的最长公共子序列（LCS）。
序列A：ABCBDAB
序列B：BDCABC

该问题需要你完成以下几个步骤：
1.状态定义：
•根据上述问题，定义动态规划中的“状态”。请描述这个状态所表达的变量或属性是什么。
2.状态转移方程：
•基于你在第一个问题中定义的状态，描述状态转移方程。请包括初始状态、结束状态以及过程中的一般状态转移。
3.边界情况：
•确定并描述这个问题的边界情况。
4.函数实现：
•使用C++或伪代码，根据你在第二个问题中描述的状态转移方程，编写一个函数。
请确保你的代码能够清楚地体现出状态转移方程。

解答：
1.状态定义
在动态规划中，我们定义状态dp［i]［j］、为序列A的前i个元素和序列B的前j
个元素之间的最长公共子序列的长度。这里dp是一个二维数组，其中i和j分
別指代序列A和B的索引。

2.状态转移方程
状态转移方程可以描述为：
•当A[i]== B[j]时，dp[i][j］= dp[i-1][j-1］+ 1。
这意味着如果当前字符匹配，则最长公共子序列长度增加1。
•当A[i]!= B[j]时，dp[i][j]=max（dp［i-1][j], dp[i][j-1］）。
这表明，如果当前字符不匹配，
我们从左边或上边的状态中选择一个更长的序列。

初始状态：dp[O][j]、和dp[i][0]应该初始化为O，因为一个空序列与任何序列的最长公共子序列长度都为0。

3.边界情况
当i=0或j=0时，表示其中一个序列为空，此时最长公共子序列长度为0。

4.函数实现

#include <stdio.h>
#include <string.h>

// 动态规划求解最长公共子序列问题
int lcs(char *A, char *B) {
    int m = strlen(A);
    int n = strlen(B);
    int dp[m+1][n+1];
    int i, j;

    // 初始化边界条件
    for (i = 0; i <= m; i++) {
        dp[i][0] = 0;
    }
    for (j = 0; j <= n; j++) {
        dp[0][j] = 0;
    }

    // 填充 dp 表
    for (i = 1; i <= m; i++) {
        for (j = 1; j <= n; j++) {
            if (A[i-1] == B[j-1]) {
                dp[i][j] = dp[i-1][j-1] + 1;
            } else {
                dp[i][j] = (dp[i-1][j] > dp[i][j-1]) ? dp[i-1][j] : dp[i][j-1];
            }
        }
    }

    return dp[m][n];
}

int main() {
    char A[] = "ABCBDAB";
    char B[] = "BDCABC";

    printf("Length of LCS is %d\n", lcs(A, B));
    return 0;
}

2、爬楼梯
小明面临着一个爬楼梯的挑战。楼梯共有n 级台阶。每次，小明可以选择爬上1级或2级台阶。
请使用动态规划的方法计算小明有多少种不同的方法来爬完这n级台阶。

1.找到状态：定义状态，以及它们代表的含义。
2.状态转移方程：描述状态之间的转换关系。
3.边界情况：确定算法的边界条件。
4.函数的编写：根据状态转移方程，使用C++或伪代码编写函数。

解答：
1、定义状态
在动态规划中，我们首先需要定义状态。在这个问题中，
我们可以定义状态dp［i］为到达第i级台阶的不同方法的数量。

2、状态转移方程
接下来，我们需要找到状态之间的转换关系，即状态转移方程。
由于小明可以选择爬1级或2级台阶，我们可以得出以下关系：
•要到达第i级台阶，小明可以从第i-1级台阶爬上一级。
•或者，他可以从第i-2级台阶爬上两级。
因此，状态转移方程为：
dp[i] = dp[i - 1] + dp[i - 2]

3、边界情况
确定算法的边界条件是非常重要的。对于这个问题：
•当n = 1时，只有一种方法爬到第一级台阶（即爬一级）。
•当n = 2时，有两种方法：爬两次一级台阶或直接爬两级台阶。
所以，边界条件为：
dp[1] = 1
dp[2] = 2
4、函数编写

#include <stdio.h>

int climbStairs(int n) {
    if (n == 1) {
        return 1;
    }
    if (n == 2) {
        return 2;
    }

    int dp[11]; // 因为台阶数量不超过10，我们可以直接定义一个大小为11的数组
    dp[1] = 1;
    dp[2] = 2;

    for (int i = 3; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }

    return dp[n];
}

int main() {
    int n;
    printf("Enter the number of stairs (up to 10): ");
    scanf("%d", &n);

    if (n > 0 && n <= 10) {
        printf("Number of ways to climb %d stairs: %d\n", n, climbStairs(n));
    } else {
        printf("Invalid number of stairs. Please enter a number from 1 to 10.\n");
    }
    
    return 0;
}

3、0/1背包问题
在一个0/1背包问题中，给定四件物品，每件物品都有其特定的重量和收益。
你的目标是确定哪些物品应该被放入背包中，以便在不超过背包最大载重
的情况下，使得背包中物品的总收益最大化。
物品的重量和收益分别是：
• 重量: w = [10,15,6,9]
• 收益：v =［2,5,8,1］
• 背包的最大载重：M = 32

请解决以下小问题：
1.状态定义：根据上述问题，定义动态规划中的“状态”。请描述这个状态表达的变量或属性是什么。
2.状态转移方程：基于你在第一个问题中定义的状态，描述状态转移方程。
请包括初始状态、结束状态以及过程中的一般状态转移。
3.边界情况：确定并描述这个问题的边界情况。
4.函数实现：使用C++或伪代码，根据你在第二个问题中描述的状态转移方程，
编写一个函数。请确保你的代码能够清楚地体现出状态转移方程。

解答：
1.状态定义
状态定义
在0/1背包问题中，状态通常是用一个二维数组来定义的，记为dp[i][j]。这里：
•i表示考虑到第i件物品（1到n）。
•j表示当前背包的重量（从O到最大载重M）。
状态dp[i][j]、表示的是在考虑前i件物品，并且当前背包重量为j时，能够获得的最大收益。

2.状态转移方程
状态转移方程
状态转移方程是基于是否选择当前的物品。对于每件物品i、和每个重量j，我们有两种选择：
•不选择当前物品（即物品1不放入背包）：此时总收益保持不变，即dp[i][j] = dp[i-1][j]。
•选择当前物品（前提是背包能够承载这个物品）：此时总收益为当前物品的收益加上
剩余重量的最大收益，即dp[i][j] = dp[i-1][j-w[i]]+v[i]，其中w[i]和
v[i]分别是物品i的重量和收益。
因此，状态转移方程为：
dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i]) if j>=w[i]
dp[i][j] = dp[i-1][j] if j < w[i]

3.边界情况是动态规划的初始化部分：
当i=0或j=0时，dp[i][j]=0。这意味着没有物品或没有背包容量时，收益为0。

4.函数实现

#include <stdio.h>

// 函数来计算最大值
int max(int a, int b) {
    return (a > b) ? a : b;
}

// 0/1背包问题的实现
int knapsack(int W, int wt[], int val[], int n) {
    int i, w;
    int dp[n + 1][W + 1];

    // 构建表格dp[][]
    for (i = 0; i <= n; i++) {
        for (w = 0; w <= W; w++) {
            if (i == 0 || w == 0) {
                dp[i][w] = 0;//边界条件
            } else if (wt[i - 1] <= w) { //装得下，装或者不装，两者取最大值
                dp[i][w] = max(val[i - 1] + dp[i - 1][w - wt[i - 1]], dp[i - 1][w]);
            } else { //装不下
                dp[i][w] = dp[i - 1][w];
            }
        }
    }

    return dp[n][W];
}

int main() {
    int val[] = {2, 5, 8, 1}; // 物品的收益
    int wt[] = {10, 15, 6, 9}; // 物品的重量
    int W = 32; // 背包的最大载重
    int n = sizeof(val) / sizeof(val[0]); // 物品的数量
    printf("最大收益是 %d\n", knapsack(W, wt, val, n));
    return 0;
}

4、投资分配问题
您作为财务分析师，有一个任务是将固定资金分配给若干个不同的投资项目，
每个项目根据不同的资金投入会有不同的收益。您的目标是在资金限制下最大化总收益。
题目的具体参数：
总资金：5万元
投资项目数：4个
每个项目有不同的收益函数 fi(x)，根据投资金额x的不同有不同的收益。
投资金额 x 必须是非负整数，且总投资额 x1 + x2 + ... + xn = m ，在本问题中 m = 5。

收益表：

投资额 x	项目 1 收益 f1(x)	项目 2 收益 f2(x)	项目 3 收益 f3(x)	项目 4 收益 f4(x)
0	0	0	0	0
1	11	0	2	20
2	12	5	10	21
3	13	10	30	22
4	14	15	32	23
5	15	20	40	24

任务：
请完成以下任务：
1. 状态定义：
根据上述问题，定义动态规划中的“状态”。描述这个状态所表达的变量或属性是什么。
2. 状态转移方程：
基于你在第一个问题中定义的状态，描述状态转移方程。请包括初始状态、结束状态以及过程中的一般状态转移。
3. 边界情况：
确定并描述这个问题的边界情况。
4. 函数实现：
使用C++或伪代码，根据你在第二个问题中描述的状态转移方程，编写一个函数。
请确保你的代码能夜清楚地体现出状态转移方程

解答：
1. 状态定义
在这个问题中，状态可以定义为一个二维数组dp[i][j]，其中i表示考虑到的项目数量（从1到4），
而j表示当前的总投资额（从0到5万元）。dp[i][j]的值代表在考虑前i个项目，
并且使用了j万元时能够获得的最大收益。

2.状态转移方程
状态转移方程描述了如何从一个状态转移到另一个状态。对于本问题，状态转移方程可以定义如下：
dp[i][j]= max（dp[i-1][j]，dp[i-1][j-k]+ fi（k））

其中i是项目索引，j是当前总资金，k是分配给项目i的资金， fi（k）是投资k万元在项目i上的收益。
这个方程意味着对于每个项目，我们可以选择不投资（即保持dp[i-1][j]），
或者投资某个金额（dp[i-1][j-k]+fi（k））。

初始状态：dp[0][j] = 0 对所有j，表示没有项目可以投资时的收益为0。

结束状态：dp[4][5] 表示考虑所有项目并使用了全部资金时的最大收益。

3.边界情況
边界情况包括：
•当j= 0时，即没有资金可用，所有dp[i][0] = 0。
•当i= 0时，即没有项目可选，所有dp[O][j] = 0。

4.函数实现

#include <stdio.h>

int max(int a, int b) {
    return (a > b) ? a : b;
}

int main() {
    int f[4][6] = {
        {0, 11, 12, 13, 14, 15},
        {0,  0,  5, 10, 15, 20},
        {0,  2, 10, 30, 32, 40},
        {0, 20, 21, 22, 23, 24}
    };

    int dp[5][6] = {0}; // 初始化dp数组

    // 第一个循环（1）：遍历所有的项目。
    // 第二个循环（j）：遍历所有的投资额。
    // 第三个循环（k）：这个循环是关键，它遍历每个项目可能的投资金额。
    for (int i = 1; i <= 4; i++) {
        for (int j = 0; j <= 5; j++) {
            for (int k = 0; k <= j; k++) {
                dp[i][j] = max(dp[i][j], dp[i - 1][j - k] + f[i - 1][k]);
            }
        }
    }

    printf("最大收益: %d\n", dp[4][5]);
    return 0;
}

5、

解答：

2.时间复杂度、空间复杂度
时间复杂度：我们需要计算L[i][j]对于每个i从1到n和每个j从1到y，所以时间复杂度为O（ny）。
空间复杂度：由于我们需要存储一个大小为n*y的二维数组，因此空间复杂度也是(ny)。

3.求解：
表格的行代表了不同的硬币种类（vi 的值），列代表了我们要兑换的金额从O到y。
每个单元格L[i,j]的值表示使用前i种硬币兑换金额j所需的最少硬币数量。

第一行（v1）：仅使用面值为1的硬币时，兑换金额j所需的硬币数量直接等于金额本身（因为每枚硬币价值1）。

第二行（v2）：现在我们引入面值为5的硬币。对于金额小于5的j，我们仍然只能使用面值为1的硬币，因此值不变。
但对于j大于或等于5，我们可以开始使用面值为5的硬币。在这些情况下，L[2,j]的值可能会变小，
因为使用面值为5的硬币可能会比仅使用面值为1的硬币需要更少的硬币数量。

第三行（v3）：引入面值为7的硬币。同样的逻辑，对于金额j大于或等于7，我们考虑使用面值为7的硬币
是否可以减少所需的硬币总数。如果可以，我们更新l[3,j]的值。

第四行（v4）：最后，我们考虑面值为11的硬币。同之前的步骤，我们检查对于金额j
大于或等于11的情况，是否使用面值为11的硬币可以减少硬币数量。

每一次，我们都是在查找最小值：是否使用新的硬币种类会比不使用它需要更少的硬币数量。如果是的话，
我们就更新那个金额的最少硬币数。

L[4][15]的值为3，表示使用前四种硬币兑换金额为15需要的最少硬币数为3。
最优解：
3枚5元硬币
2枚7元硬币+1枚1元硬币
最优值：3

	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
v1	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
v2	1	2	3	4	1	2	3	4	5	2	3	4	5	6	3
v3	1	2	3	4	1	2	1	2	3	2	3	2	3	2	3
v4	1	2	3	4	1	2	1	2	3	2	1	2	3	2	3

贪心算法大题

0、考察重点
题3，第四章贪心
关键词
1、思路，构造局部最优的策略
2、时间复杂度（关键步骤在哪里）

1、对下图所示的连通网络G，用克鲁斯卡尔(Kruskal)/Prim算法求G的最小生成树T,
请写出在算法执行过程中，依次加入T的边集TE中的边。说明该算法的贪心策略和算法的基本思想，
并简要分析算法的时间复杂度。

解答：
a.
使用克鲁斯卡尔算法对提供的图G求最小生成树T的过程如下：
1. 首先，我们将所有边按照权重从小到大排序。
2. 然后，逐一考虑每条边，确保加入的边不会与已选的边集TE形成环。
3. 不断重复上述过程，直到形成最小生成树T。

按照这个过程，依次加入到最小生成树T的边集TE中的边为：
(4, 3, 6)
(2, 3, 7)
(1, 5, 11)
(6, 4, 15)
(5, 4, 17)
这些边依次被加入到最小生成树中，形成最终的最小生成树。

算法的贪心策略：
克鲁斯卡尔算法的贪心策略在于每次选择连接两个不同子集的最小边，这保证了每次
加入到生成树T中的边都是当前可用边中最小的，从而确保最终形成的生成树的总权重尽可能小。

算法的基本思想：
算法的基本思想是通过局部最优选择（每次选择最小的边）来达到全局最优解（最小生成树的最小总权重）。
或者
将所有边按权值升序排列，依次选边，只要不构成回路就选，直到n-1条边。

时间复杂度分析：
克鲁斯卡尔算法的时间复杂度主要由排序和查找最小边的操作决定。排序的时间复杂度是O（ElogE），
其中E是边的数量。查找和合并操作可以通过优化后的并查集操作进行，时间复杂度接近O（1），
因此整体算法的时间复杂度是O（ElogE）。

b.
使用Prim算法对提供的图G求最小生成树T的过程如下：
初始化：选择一个顶点作为起始点，并将其标记为已访问。初始化一个记录最小权重的数组，
初始时除了起始顶点外，所有顶点的权重设置为无穷大。
选择边并更新权重：从所有未访问的顶点中，选择一条权重最小且连接到已访问顶点的边。
将这条边及其连接的顶点加入到最小生成树中，并更新未访问顶点到已访问顶点集的最小权重。
构建最小生成树：重复步骤2，直到所有顶点都被访问。每次迭代选择一条新边加入到最小生成树中，
直到连接所有顶点。

按照Prim算法的过程，依次加入到最小生成树T的边集TE中的边为：
(1, 5, 11)
(5, 4, 17)
(4, 3, 6)
(3, 2, 7)
(4, 6, 15)

这些边按照它们被加入到最小生成树中的顺序列出。

算法的贪心策略：
Prim算法的贪心策略在于每次选择当前可用的最小的边加入到生成树中，
确保每次加入的边都能使得生成树的权重增长最小。

时间复杂度分析：
Prim算法会从一个顶点开始，然后在每一步选择一个与当前最小生成树边权最小的边来扩展这棵树。
在使用数组的情况下，每次找到这样一条边需要遍历所有的边，因此每次操作的复杂度是O(V)。
由于算法需要选择V-1条边来形成最小生成树（一个有V个顶点的图的最小生成树有V-1条边），
所以总的时间复杂度是O(V^2)。

2、考虑用哈夫曼算法来找字符a,b,c,d,e,f 的最优编码。
这些字符出现在文件中的频数之比为20:10:6:4:44:16。要求：
(1)简述使用哈夫曼算法构造最优编码的基本步骤；
(2)构造对应的哈夫曼树，并据此给出a,b,c,d,e,f 的一种最优编码。
(3)分析时间复杂度

解答：
(1)
基本步骤：
1. 初始化森林
每个字符都对应一棵仅包含单个结点的树，这个结点是树的根，其权值（根权）是该字符在文件中的频率。
这些单结点树构成了一个森林。
2. 合并过程
在接下来的每一步中，都会在森林中选取根权最小的两棵树。这两棵树被合并成一棵新树，新树的根结点
是两个原始根结点的父节点。新根的权值是两个子树根权之和。
3. 重复合井
这个合并过程会重复进行，每次都减少森林中树的数量，直到最后只剩下一棵树。这棵最终的树就是哈夫曼树。
4. 编码生成
在最终的哈夫曼树中，每个原始字符对应的结点到根结点的路径定义了该字符的编码。一般约定向左的路径
表示“O”，向右的路径表示“中”。
通过这个方法，哈夫曼算法确保了频率较高的字符有较短的编码，而频率较低的字符有较长的编码，
从而实现了数据的有效压缩。

(2)
构造的哈夫曼树编码：
a：10
b：1111
c：11101
d：11100
e：0
f：110

3、时间复杂度为O(nlogn)

3、通过键盘输入一个高精度的正整数n（n的有效位数≤240），去掉其中任意s个数字后，
剩下的数字按原左右次序将组成一个新的正整数。对给定的n和s，
寻找一个方案，使得剩下的数字组成新的最小的正整数。
如输入n为178543，s为4，结果为13
试用贪心法解决此问题，请：
(1) 给出用贪心法求解该最优化问题的贪心选择策略。
(2) 请补全下列贪心算法求出对正整数n去掉s个数字之后得到的新的最小的正整数。
(3) 此算法的渐进时间复杂度？

解答：
1、
贪心算法在每一步选择中都采取在当前看来最好的选择，希望通过局部最优的选择来达到全局最优的结果。
在这个问题中，我们的目标是在去除s个数字后得到一个尽可能小的新整数。因此，贪心策略如下：

从左到右遍历数字n，每次找到一个数字，如果这个数字大于其后面的数字，就将其删除。
这样做的理由是，删除较大的数字能更快地减小整体值。
重复这个过程，直到删除了s个数字或者没有更多可以删除的数字（因为剩余的数字是升序排列的）。

2、略。

3、
关于算法的时间复杂度，我们需要考虑两个主要因素：数字n的长度和我们需要删除的数字数量S。
最坏情况下，算法可能需要遍历整个数字n以找到要删除的数字，这需要O(n)时间，
其中n是数字的长度。因为这个过程最多重复s次，所以总的时间复杂度是O(n*s).
综上所述，这个贪心算法的渐进时间复杂度是O（n*s）。

4、请写出 Dijkstra 算法的具体计算步骤，并根据代码求从定点a到其它所有顶点的最短距离。
并分析该算法的时间复杂度

解答：
Dijkstra算法是一种用于在加权图中找到最短路径的算法。它从源节点开始，逐渐扩展到图中的所有节点，
为每个节点维护当前找到的从源节点到该节点的最短路径。具体的计算步骤如下：
1. 创建两个集合：已确定最短路径的节点集合（S）和未确定最短路径的节点集合（Q）。
2. 将所有节点的最短路径估计值初始化为无穷大，源节点的最短路径值初始化为0。
3. 将所有节点放入集合Q中。
4. 当集合Q非空时：
a. 从Q中选择一个距离最小的节点u（初始时为源节点）。
b.将u从Q中移除并放入S中。
c.对于每个从u出发的边（u,v），如果v在Q中，则更新v的最短路径值：
如果通过u到v的路径比当前记录的路径更短，则更新它。
重复这个过程，直到集合Q为空。集合S中的每个节点的最短路径值就是从源节点到该节点的最短路径长度。

根据Dijkstra算法计算的结果，从顶点a到其它所有顶点的最短距离如下：
• a到a的最短距离是O（因为它是起点）
• a到b的最短距离是2
• a到c的最短距离是3
• a到e的最短距离是9
• a到f的最短距离是6
• a到h的最短距离是10

在这种实现中，我们在每一步都需要O（n）的时间来找到未处理的最小距离顶点，
并且我们需要进行n次这样的步骤（因为每个顶点都需要被处理一次）。因此，总时间复杂度是O(n^2).

5、

解答：
1.基本思路
Dijkstra算法是一种用于在加权图中找到从单个源到所有其他节点的最短路径的算法。基本思路是这样的：

初始化：将所有节点标记为未访问，给每个节点一个距离值，源节点为0，所有其他节点为无限大。
对所有未访问节点，选择距离最小的节点，称为当前节点。
更新当前节点所有未访问的邻居的距离值：如果通过当前节点到邻居节点的距离小于已知的距离，则更新该距离。
当前节点标记为已访问。
重复上述步骤直到所有节点都被访问。

2.
在图1中，我们看到有向图中有些边的权值是负数。如我之前所述，Dijkstra算法不能正确处理带有负权边的图。在Dijkstra算法中，一旦一个节点的最短路径被确定，该节点就会被标记为已访问，并且其最短路径长度不会被后续的操作改变。但是，在存在负权边的情况下，一个节点的最短路径可能会因为之后的计算而变短，这违反了Dijkstra算法的基本假设。

具体来说，如果你先访问了节点s到节点a的路径（假设其权值为正数），然后访问了节点a到节点b的路径，如果a到b的路径权值为负数，并且其绝对值足够大，那么这会导致从s到b的总路径长度减少。这意味着在算法执行过程中，之前确定的最短路径可能不再是最短的。

因此，在图1这样含有负权边的图中，我们不能使用Dijkstra算法来找到从源节点s到其它所有节点的最短路径。需要使用其他算法，如Bellman-Ford算法，它能够处理负权边并且能够在图中存在负权环时报告无解。

3.计算过程、计算结果

回溯算法大题

0、考察重点
题4，第五章回溯

关键词
1、解空间，构造是关键
2、两个基本的类型（a.子集树 b.排列树）
注：
1、画出树，解结构的形态
2、求解最优，并解释表达的内涵

1、求解子集和数的问题：设有n=4个正数的集合S={1,2,6,8}和整数M=9，
请画出回溯法求解过程中产生的状态空间树，并给出所有子集和为M的可行解（x0,x1,x2,x3）。

解答：
状态空间树：

所有子集和为M的可行解
（1，1，1，0）
（1，0，0，1）

这种表达方式（1, 1, 1, 0）和（1, 0, 0, 1）是在说，
每个数字代表一个决策：1 表示包括该元素，0 表示不包括。
因此，(1, 1, 1, 0) 表示包括 {1, 2, 6} 这三个元素，而 (1, 0, 0, 1) 表示包括 {1, 8} 这两个元素。

所以，正确的答案是：
所有子集和为 M 的可行解为 (1, 1, 1, 0) 和 (1, 0, 0, 1)，分别对应于子集 {1, 2, 6} 和 {1, 8}。

2、请画出用回溯法解4皇后问题的解空间树和搜索空间树：

解答：
略。

3、请画出用回溯法解n=3的0-1背包问题的解空间树和当三个物品的重量为{20, 15, 10}，
价值为{20, 30, 25}，背包容量为25时搜索空间树。 

解空间树如下图：
最优解为：
(0,1,1)
最优值为55

4、子集和数的问题：设有n=4个正数的集合W={w0,w1,w2,w3}={7,11,13,24}和正数M=31，
求W的所有满足条件的子集，使子集中的正数之和等于M。
请画出由SumOfSub算法实际生成的那部分状态空间树，并给出所有可行解。（采用固定长度4-元组表示解）

解答：
状态空间树如下图所示：
可行解：
(1,1,1,0)
(1,0,0,1)

5、0-1背包问题
假设你有一个背包，最大承重为W，以及一系列物品，每个物品都有自己的重量和价值。
目标是选择一些物品放入背包中，使得所选物品的总价值最大，同时不超过背包的承重限制。
物品的重量和收益分别是：
• 重量: w = [10,15,6,9]
• 收益：v =［2,5,8,1］
• 背包的最大载重：M = 32
任务：
1. 解空间的构造：
描述0-1背包问题的解空间如何构造。解释这个解空间的结构是如何与子集树相关的。
2. 绘制解空间树：
给定一个简单的物品列表，画出对应的子集树。标注出每个节点的决策（是否选择该物品）。
3. 求解最优解：
通过回溯算法在你绘制的树上求解最优解。解释在此过程中如何剪枝优化搜索。
4. 最优解的内涵解释：
解释在0-1背包问题中最优解的含义。

1.解空间的构造
0-1背包问题的解空间可以构造为一个子集树。在这个树中，每个节点代表一个决策-是否将特定的物品放入背包中。

每层代表一个物品。
每个节点有两个分支：一个代表选择当前物品（将其放入背包），另一个代表不选择（不将其放入背包）。
解空间的每个路径（从根到叶的路径）代表一个可能的物品组合。

0-1背包问题的解空间结构与子集树紧密相关，因为这个问题本质上是在寻找一个物品的子集，
该子集的总重量不超过背包的最大承重，同时总价值最大化。这里的关键在于选择物品的组合，这正是子集树所表示的。

2.解空间树的绘制：
左分支表示选择该物品，右分支表示不选择该物品。

3.求解最优解：
在绘制的树上使用回溯算法时，您可以通过检查当前的总重量是否超过
背包的最大载重来剪枝。如果超过，则终止当前分支的搜索。此
外，您还可以通过比较当前的总价值与已知最优解的价值来剪枝。
如果当前分支即使加上所有剩余物品的价值也无法超过已知的最优解，则该分支不会产生更好的结果，可以被剪掉。

4. 最优解的内涵解释：
在0-1背包问题中，“最优解”是指在不超过背包承重限制的条件下，可以获得的最大总价值的物品组合。
这通常涉及在物品的重量和价值之间进行权衡，找到最佳组合以最大化价值。
您的解决方案选择了前三个物品，即w =［10,15,6］和v=［2,5,8］，
总重量是10+15+6=31，总价值是2+5+8=15。这个总重量没有超过背包的最大载重M=32，
并且在不违反此限制的情况下，您已经找到了最大的总价值，所以这确实是最优解。

6、旅行商问题（TSP）
假设有一组城市和每对城市之间的旅行成本，目标是找到一条最短的路径，
访问每个城市恰好一次，并最终返回出发城市。
城市集合和路径成本信息如下：

城市集合：｛1,2,3,4｝
成本：
• 1到2的成本是5
• 1到3的成本是9
• 1到4的成本是4
• 2到3的成本是13
• 2到4的成本是2
• 3到4的成本是7

任务：
1. 解空间的构造：
描述TSP问题的解空间如何构造。解释这个解空间的结构是如何与排列树相关的。
2. 绘制解空间树：
画出对应的排列树。标注出每个节点的决策（选择下一个访问的城市）。
3. 求解最优解：
通过回溯算法在你绘制的树上求解最优解。解释在此过程中如何剪枝优化搜索。
4. 最优解的内涵解释：
解释在TSP问题中最优解的含义。

解答：
1.解空间的构造
TSP问题的解空间是通过城市的所有可能排列来构建的。这个解空间的结构是与排列树相关的，
排列树是一个有序树，通常用来表示对象的所有可能排列。
•树的节点：代表一个部分解，即到目前为止的路径。
•树的边：代表从一个城市到另一个城市的决策。
•叶节点：代表完成的路径，即访问了所有城市一次并返回出发城市的路径。

2.解空间树
假设有4个城市，我们可以用排列树来表示所有可能的路径。以下是一个简化的排列树示例：
             (1)         
          /   |   \      
         /    |    \     
       (2)   (3)   (4)   
      /  \   / \   /  \  
    (3) (4)(2) (4)(2) (3)
    |    |   |   |   |   |
   (4)  (3) (4) (2) (3) (2)

在这棵树中，我们从城市1开始，然后选择下一个要访问的城市，直到访问了所有的城市。

3.求解最优解
使用回溯算法求解最优解时，我们可以通过当前路径的总成本以及剩余城市的最小可能成本来剪枝。
•成本剪枝：如果当前路径的总成本已经超过了已知的最低成本路径，那么这个分支就不会产生最优解，可以被剪掉。
•界限函数：可以用来估计完成当前路径所需的最小成本，如果该成本大于已知的最低成本，则当前路径不再考虑。

以下排列成本为：
• 1-2-3-4-1:29
• 1-2-4-3-1:23
• 1-3-2-4-1:28
• 1-3-4-2-1:23
• 1-4-2-3-1:28
• 1-4-3-2-1:29
最优解的路径是1-2-4-3-1，总成本为23。这条路径访问了每个城市一次，并且总旅行成本是最低的。

4. 最优解的内涵解释
在TSP问题中，最优解是指访问每个城市恰好一次，并返回出发城市的路径中，总旅行成本最低的路径。
这意味着，如果我们有多条可能的路径，最优解是这些路径中总成本最低的那一条。

7、装载问题

有一艘船和一系列货物，假设船容量为8，货物有3个，重量分别为5，3，1。
要求重量最大，不能超重。

任务：
1.解空间的构造：
描述装载问题的解空间如何构造。解释这个解空间的结构是如何与子集树相关的。
2.绘制解空间树：
画出对应的子集树。标注出每个节点的决策（选择将该货物装载到哪艘船上）。
3.求解最优解：
通过回溯算法在你绘制的树上求解最优解。解释在此过程中如何剪枝优化搜索。
4.最优解的内涵解释：
解释在装载问题中最优解的含义。

解答：
1.解空间的构造
装载问题的解空间可以通过构建一个子集树来表示，其中每个节点代表一个装载决策阶段。
这个解空间的结构与子集树相关，因为我们在每个阶段都在做选择一要么将货物装入船中，要么不装。
•树的节点：代表一个部分解决方案，即在某一阶段货物的装载状态。
•树的边：表示是否选择将当前考虑的货物装入船中。左分支可以代表选择装载当前货物，右分支代表不装载。
•树的深度：等于货物的数量，每个层级代表对一个新货物的装载决策。

2.绘制解空间树

每个分支代表一个货物的装载决策，例如，左边的分支代表装载当前货物，右边的分支代表不装载。

3.求解最优解
通过回溯算法在树上求解最优解时，我们会跟踪当前的装载量，并确保它不超过船的最大载重量。
我们可以通过以下方式进行剪枝：
•如果任何决策导致当前装载量超过最大载重量，那么这个决策路径会被剪掉。
•如果当前的决策路径已经达到或超过了最大可能装载量，那么无需进一步探索该路径。

4.最优解的内涵解释
在装载问题中，最优解是指在不超过船的最大载重量的前提下，可以装载的最大货物重量。
这通常意味着尽量装满船的容量，而不是平衡不同船只的装载量，因为这里只有一艘船。
对于给定的例子，我们的目标是装载尽可能多的货物，直到达到船的最大载重量为止。

在这个特定的例子中，我们可以将重量为5和3的货物装入船中，总重量为8，
这是在不超重的条件下的最优解是将重量为5和3的货物装入船中，总装载重量为8。

填空：

1、【算法】由有限条指令构成，每条指令规定了计算机所要执行的有限次运算或者操作。

2、一个最优决策序列的任何子序列本身一定是相对于子序列的【初始和结束状态】的最优的决策序列.

3、贪心算法的证明通常需要证明该算法能够找到问题的最优解。除了数学归纳法之外，还有【交换论证法/反证法】证明方法。

4、分治算法通常都是递归算法，这种算法的时间复杂度分析通常需要求解【递推方程】。

5、可行流f是最大流的充分必要条件是不存在关于f的s-t【增广链】。

选择：

无。

大题：

1、归并排序

没啥好说的。

2、田忌赛马

二千多年前的战国时期，齐威王与大将田忌赛马。双方约定每人各出300匹马，并且在
上、中、下三个等级中各选一匹进行比赛，由于齐威王每个等级的马都比田忌的马略强，
比赛的结果可想而知。现在双方各n匹马，依次派出一匹马进行比赛，每一轮获胜的一方
将从输的一方得到200银币，平局则不用出钱，田忌已知所有马的速度值并可以安排出场
顺序，问他如何安排比赛获得的银币最多。

参考答案：

3、解空间树绘制、最优解，最优值，含义解释

4、动态规划问题-小民走迷宫

int minPathForDP(){
    // 边界情况
    dp[0][0] = a[0][0];
    for(int j = 1; j <n; j++) {
        dp[0][j] = dp[0][j-1] + a[0][j];
    }
    for(int i = 1; i <m; i++) {
        dp[i][0] = dp[i-1][0] + a[i][0];
    }
    
    for(int i = 1; i <m; i++) {
        for(int j = 1; j <n; j++) {
            dp[i][j] = a[i][j] + min(dp[i-1][j], dp[i][j-1]);
        }
    }
    return dp[3][3];
}