• 期末算法复习

    0-1背包问题（动态规划）

    例题

    算法思想：

    动态规划的核心思想是将原问题拆分成若干个子问题，并利用已解决的子问题的解来求解更大规模的问题。

    主要是状态转移方程和状态

            

    算法描述：

    1. 初始化一个二维数组dp，大小为(n+1)×(W+1)，其中n为物品的个数，W为背包的容量限制。
    2. 将dp数组的第0行和第0列全部初始化为0，表示背包容量为0或物品个数为0时的最大总价值都为0。
    3. 对于物品i，从1到n，依次进行以下操作：
      • 对于背包容量j，从1到W，依次进行以下操作：
        • 如果第i个物品的重量小于等于背包容量j，则可以选择装入该物品或不装入该物品，选择其中总价值较大的方案：
          • 如果选择装入该物品，则总价值为dp[i-1][j-w[i]] + v[i]，其中w[i]为第i个物品的重量，v[i]为第i个物品的价值；
          • 如果选择不装入该物品，则总价值为dp[i-1][j]。
          • 取两者中的较大值作为dp[i][j]的值。
        • 如果第i个物品的重量大于背包容量j，则无法选择装入该物品，只能选择不装入该物品，即dp[i][j] = dp[i-1][j]。
    4. 最终的dp[n][W]即为问题的解，表示在物品个数为n，背包容量为W时的最大总价值。

    复杂度分析：

    • 时间复杂度：动态规划解法的时间复杂度为O(nW)，其中n为物品的个数，W为背包的容量限制。
    • 空间复杂度：动态规划解法的空间复杂度为O(nW)，需要使用一个二维数组dp来记录子问题的最优解，若是使用滚动数组优化，可以减小空间复杂度，实际上只用开一维数组，O(W)。

    正确性分析：

    代码：

    1. // 代码一：
    2. import java.util.Scanner;
    3. public class Main {
    4.     public static void main(String[] args) {
    5.         int n, W;
    6.         int[] v = new int[110], w = new int[110];
    7.         int[][] dp = new int[110][110];
    8.         Scanner scanner = new Scanner(System.in);
    9.         W = scanner.nextInt();
    10.         n = scanner.nextInt();
    11.         for(int i = 1; i <= n; i ++ ) {
    12.             w[i] = scanner.nextInt();
    13.             v[i] = scanner.nextInt();
    14.         }
    15.         for(int i = 0; i <= W; i ++ ) dp[0][i] = 0;
    16.         for(int i = 1; i <= n; i ++ ) {
    17.             for(int j = 0; j <= W; j ++ ) {
    18.                 dp[i][j] = dp[i - 1][j];
    19.                 if (j >= w[i]) dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - w[i]] + v[i]);
    20.             }
    21.         }
    22.         System.out.println(dp[n][W]);
    23.     }
    24. }
    25.  
    26. // 代码二：（滚动数组优化）
    27. import java.util.Scanner;
    28.  
    29.  
    30. // in:
    31. //70 3
    32. //71 100
    33. //69 1
    34. //1 2
    35. public class Main {
    36.     public static void main(String[] args) {
    37.         int n, W;
    38.         int[] v = new int[110], w = new int[110];
    39.         int[] dp = new int[1010];
    40.         Scanner scanner = new Scanner(System.in);
    41.         t = scanner.nextInt();
    42.         m = scanner.nextInt();
    43.         for(int i = 1; i <= n; i ++ ) {
    44.             w[i] = scanner.nextInt();
    45.             v[i] = scanner.nextInt();
    46.         }
    47.         for(int i = 0; i <= W; i ++ ) dp[i] = 0;
    48.         for(int i = 1; i <= n; i ++ ) {
    49.             for(int j = W; j >= w[i]; j -- ) {
    50.                 dp[j] = Math.max(dp[j], dp[j - w[i]] + v[i]);
    51.             }
    52.         }
    53.         System.out.println(dp[W]);
    54.     }
    55. }

    单源最短路径dijkstra（贪心）

    算法思想：

    Dijkstra算法用于求解单源最短路径问题，即从给定的起点到其他所有节点的最短路径。该算法采用贪心的策略，通过逐步扩展已经确定最短路径的节点集合，来逐步求解所有节点的最短路径。

    算法描述：

    1. 初始化：将起点s到所有其他节点的距离设置为无穷大，将起点s到自身的距离设置为0。
    2. 创建一个优先队列（最小堆）Q，将起点s加入Q。
    3. while Q不为空：
      • 从Q中选择距离最小的节点u，将u从Q中移除。
      • 对于u的所有邻接节点v：
        • 计算s到v的距离d，即通过u到v的距离加上s到u的距离。
        • 如果d小于v当前的距离，则更新v的距离。
        • 如果v不在Q中，则将v加入Q。
    4. 返回起点s到所有其他节点的最短路径。

    复杂度分析：

    • 时间复杂度：在每次循环中，需要从Q中选择距离最小的节点，这需要O(V)的时间，其中V是顶点的数量。对于每个节点，需要更新其邻接节点的距离，这需要O(E)的时间，其中E是边的数量。因此，总的时间复杂度为O((V + E) * log V)，其中log V是从Q中选择最小值的时间复杂度。
    • 空间复杂度：需要使用一个大小为V的优先队列来保存节点，以及一个大小为V的数组来保存每个节点的距离。因此，总的空间复杂度为O(V)。

    正确性分析：

    • Dijkstra算法通过贪心策略来逐步扩展已经确定最短路径的节点集合，从而求解所有节点的最短路径。该算法的正确性基于贪心选择性质，即每次选择距离最小的节点更新其邻接节点的距离，可以保证得到正确的最短路径。
    • 此外，Dijkstra算法还需要满足非负权重的条件，即边的权重不能为负数。如果存在负权重的边，则需要使用其他算法，如Bellman-Ford算法。

    代码：

    1. // 朴素版：
    2. int dijkstra()
    3. {
    4.     memset(dist, 0x3f, sizeof(dist));
    5.     dist[1] = 0;
    6.     for(int i = 1; i <= n; i++)
    7.     {
    8.         int t = -1;
    9.         for(int j = 1; j <= n; j++)
    10.         {
    11.             if(!visited[j] && (t == -1 || dist[j] < dist[t]))
    12.                 t = j;
    13.         }
    14.         visited[t] = true;
    15.         for(int j = 1; j <= n; j++)
    16.             dist[j] = min(dist[j], dist[t] + g[t][j]);
    17.     }
    18.     if(dist[n] == 0x3f3f3f3f) return -1;
    19.     return dist[n];
    20. }
    21.  
    22. // 堆优化版：用邻接表存
    23. int dijkstra(int s)
    24. {
    25.     memset(dist, 0x3f, sizeof(dist));
    26.     dist[s] = 0;
    27.     priority_queue, greater> heap; // 定义一个小根堆
    28.     heap.push({0, s}); // 这里显然要根据距离排序
    29.     while(heap.size())
    30.     {
    31.         PII k = heap.top(); // 取不在集合S中距离最短的点
    32.         heap.pop();
    33.         int ver = k.second, distance = k.first;
    34.  
    35.         if(st[ver]) continue;
    36.         st[ver] = true;
    37.  
    38.         for(int i = h[ver]; i != -1; i = ne[i])
    39.         {
    40.             int j = e[i]; // i只是个下标，e中在存的是i这个下标对应的点。
    41.             if(dist[j] > distance + w[i])
    42.             {
    43.                 dist[j] = distance + w[i];
    44.                 heap.push({ dist[j], j });
    45.             }
    46.         }
    47.     }
    48.     if(dist[n] == 0x3f3f3f3f) return -1;
    49.     else return dist[n];
    50. }

    矩阵连乘问题（动态规划）

    算法思想：

    矩阵链乘法问题是关于如何以最佳方式对一系列矩阵进行乘法计算，以最小化标量乘法操作的次数。为了实现这一目的，常用动态规划来解决。

    假设我们有一系列矩阵 ( A_1, A_2, ..., A_n )，其中矩阵 ( A_i ) 的维度为 ( p_{i-1} \times p_i )。我们的目标是找到一种括号化方式，使得计算这些矩阵乘积所需的标量乘法次数最少。

    动态规划的基本思想是利用子问题的最优解构造全局最优解。我们定义一个二维数组 ( m[i][j] ) 来表示计算矩阵 ( A_i ) 到 ( A_j ) 之间连乘所需的最小标量乘法次数。

    一般只需要最后一个矩阵的列数。

    • s[i][j] 记录了在 i 到 j 范围内，使得乘法次数最小的分割点 k。

    通过递归地划分问题并结合子问题的解，我们可以构建出整个问题的最优解。

    算法描述：

    复杂度分析：

    • 时间复杂度: 外层循环有 (n-1) 次迭代（链长度从2到n），第二个循环有 (n) 次迭代，内循环最多有 (n) 次迭代，因此总的时间复杂度为 (O(n^3))。
    • 空间复杂度: 我们需要一个 (n \times n) 的二维数组来存储中间结果，因此空间复杂度为 (O(n^2))。

    正确性分析：

    1. 子问题的定义: 我们定义 (m[i][j]) 为计算矩阵 (A_i) 到 (A_j) 连乘所需的最小标量乘法次数。

    2. 边界条件: 当只有一个矩阵时，乘法次数为零，即 (m[i][i] = 0)。

    3. 状态转移方程: 对于 (i \le j)，我们尝试所有可能的分割点 (k)，计算 (m[i][j]) 的最小值，即

      m[i][j] = min{ m[i][k] + m[k+1][j] + p[i-1] * p[k] * p[j] } 

    代码：

    1. // p[]存放的是所有矩阵的行数和最后一个矩阵的列数
    2. void matrixchain() {
    3. 	memset(m, 0, sizeof(m));
    4. 	memset(s, 0, sizeof(s));//初始化数组
    5. 	for(int r=2; r<=n; r++)//矩阵连乘的规模为r 
    6.     {
    7. 		for(int i=1; i <= n-r+1; i ++ ) // 遍历每一种起点
    8. 		{
    9. 			j = i+r-1;
    10. //  加的认准三个m[i][j]+m[k][w] + p[i - 1] + p[j] + p[w]
    11. 			m[i][j]=m[i+1][j]+p[i-1]*p[i]*p[j]; // 初始假设将所有矩阵都与第一个矩阵相乘
    12.             s[i][j]=i; // s[][]存储各子问题的决策点，即下标
    13. 			for(int k=i+1; k < j; k++) // 寻找最优值
    14. 			{
    15. 				int t=m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j];
    16. 				if(t < m[i][j])
    17. 				{
    18. 					m[i][j]=t;
    19. 					s[i][j]=k;
    20. 				}
    21. 			}
    22. 		}
    23. 	}
    24. }
    25. // 决策点用来决定打印的加括号的位置
    26. void print(int i,int j) {
    27. 	if(i == j)
    28. 	{
    29. 		cout<<"A["<<i<<"]";
    30. 		return;
    31. 	}
    32. 	cout<<"(";
    33. 	print(i,s[i][j]);
    34. 	print(s[i][j]+1,j);//递归1到s[1][j]
    35. 	cout<<")";
    36. }

    最长公共子序列（动态规划）

    算法思想：

    CS问题可以通过动态规划方法来解决。基本思想是使用一个二维数组存储子问题的解，从而避免重复计算。具体步骤如下：

    1. 定义状态：设 dp[i][j] 表示序列 X[1..i] 和 Y[1..j] 的最长公共子序列的长度。
    2. 状态转移方程：
      • 如果 X[i] == Y[j]，则 dp[i][j] = dp[i-1][j-1] + 1；
      • 如果 X[i] != Y[j]，则 dp[i][j] = max(dp[i-1][j], dp[i][j-1])。
    3. 初始条件：当任何一个序列为空时，最长公共子序列的长度为0，即 dp[i][0] = dp[0][j] = 0。

    算法描述：

    function LCS(X, Y):
        m = length(X)
        n = length(Y)
        
        # 创建二维数组 dp
        dp = array of size (m+1) x (n+1) initialized to 0
        
        # 填充 dp 表
        for i from 1 to m:
            for j from 1 to n:
                if X[i-1] == Y[j-1]:
                    dp[i][j] = dp[i-1][j-1] + 1
                else:
                    dp[i][j] = max(dp[i-1][j], dp[i][j-1])
        
        # 返回最终结果
        return dp[m][n]
     

    复杂度分析：

    时间复杂度

            填充一个大小为 (m+1) x (n+1) 的二维数组，每个元素的计算时间为常数时间。因此，总的时间复杂度为 O(m * n)，其中 m 和 n 分别是序列 X 和 Y 的长度。

    空间复杂度

            空间复杂度主要取决于用于存储 dp 数组的空间。二维数组 dp 的大小为 (m+1) x (n+1)，所以空间复杂度为 O(m * n)。但是，可以通过空间优化技术（例如使用滚动数组）将空间复杂度降低到 O(min(m, n))。

    正确性分析：

    基础情况正确性
    • 当 i=0 或 j=0 时，dp[i][0] 和 dp[0][j] 都初始化为0，这表示空序列与任何序列的LCS长度为0，这是正确的。
    递推关系正确性
    • 当 X[i-1] == Y[j-1] 时，dp[i][j] = dp[i-1][j-1] + 1，这表示当前字符相等时，最长公共子序列长度增加1。
    • 当 X[i-1] != Y[j-1] 时，dp[i][j] = max(dp[i-1][j], dp[i][j-1])，这表示要么不包括 X[i-1]，要么不包括 Y[j-1]，取两者中较大者作为当前子问题的解。

    代码：

    1. #include
    2. #include 
    3. using namespace std;
    4.  
    5. const int N = 1e4 + 10;
    6. string str1, str2;
    7. int c[N][N];
    8. void LCS() {
    9.     for(int i = 0; i < str1.size(); i ++ ) {
    10.         for(int j = 0; j < str2.size(); j ++ ) {
    11.             if(str1[i] == str2[j]) c[i + 1][j + 1] = c[i][j] + 1;
    12.             else c[i + 1][j + 1] = max(c[i][j + 1], c[i + 1][j]);
    13.         }
    14.     }
    15.     
    16.     cout << c[str1.size()][str2.size()] << endl;
    17. }
    18.  
    19. int main() {
    20.     cin >> str1 >> str2;
    21.     
    22.     LCS();
    23.     return 0;
    24. }

    作业调度问题（回溯法）

            每一个作业Ji都有两项任务分别在2台机器上完成。每个作业必须先有机器1处理，然后再由机器2处理。作业Ji需要机器j的处理时间为tji。对于一个确定的作业调度，设Fji是作业i在机器j上完成处理时间。则所有作业在机器2上完成处理时间和f=F2i，称为该作业调度的完成时间和。当作业以相同次序在机器1和机器2上完成处理时，可以得到一种最佳调度，即使该作业调度的完成时间和最小。

    算法思想：

    对于给定的n个作业，指定最佳作业调度方案，使其完成时间和最小，因此是求一个最优值。
    调度必须遵循：
            ① 一个作业必须先由机器1处理，再由机器2处理，顺序不可颠倒；
            ② 机器1处理n个作业的顺序必须和机器2处理n个作业的顺序相同（因为只有这样才能使作业调度的完成时间和最小）。
    由于是一种作业调度顺序的方案，因此该问题的解空间树是排列树。

    算法描述：

    复杂度分析：

    时间复杂度

    • 在最坏情况下，回溯法需要考虑所有可能的解，因此时间复杂度通常为指数级别，即 O(2^n)，其中 n 是作业的数量。
    • 实际应用中，通过剪枝（约束条件的合理设置）可以显著减少搜索空间，提高效率。

    空间复杂度

    • 回溯法通常只需要辅助空间来存储当前状态和最优解的临时变量，因此空间复杂度较低，通常为 O(n)，其中 n 是作业的数量。

    正确性分析：

    如何判断某个作业需要在机器2上完成的任务何时开始，这个节点是上一个作业在机器2上完成处理的时间和本作业在机器1上完成处理的时间的较大者

    代码：

    1. void Backtrack(int i)
    2. {
    3.     if(i>n)   //每到达一个叶子结点，一定是产生了一个最优解，因此要更新之前最优解的值
    4.     {
    5.         if(f//更新最优解
    6.         {
    7.             for(int j=1;j<=n;j++)
    8.                 bestx[j]=x[j];
    9.             bestf=f;
    10.         }
    11.     }
    12.  
    13.     else
    14.     {
    15.         for(int j=i;j<=n;j++)   //控制展开i-1层结点的各个分支。例如当i=1时，表示在整棵排列树的根结点处，刚要开始探索结点，这时可以展开的分支有1、2、3……
    16.         {
    17.             f1+=M[x[j]][1];   //计算第i层（个）作业在机器1上的完成处理的时间
    18.             if(f2[i-1]>f1)   //如果第（i-1）个作业在机器2上的完成处理的时间大于第i个作业在机器1上的完成处理的时间，那么第i个作业想进入机器2，就要等第（i-1）个作业在机器2上完成后再说
    19.                 f2[i]=f2[i-1]+M[x[j]][2];
    20.             else   //否则，第i个作业可以在机器1上完成处理后直接进入机器2。
    21.                 f2[i]=f1+M[x[j]][2];
    22.             f+=f2[i];   //计算完第i个作业在机器2上的完成处理的时间，就可以计算出前i个作业在机器2上完成处理的时间和了
    23.             if(f//截止到这，已经得到一个前i个作业在机器2上完成处理的时间和f，如果f比之前记录的前i个作业在机器2上的完成处理的时间和的最优值bestf都要小，就可以生成第i层结点的孩子结点，继续探索下一层
    24.             {
    25.                 Swap(x[i],x[j]);   //把处于同一层的并且使f更小的那个结点拿过来，放到正在探索的这个结点处（这里结合排列数的图可以更好地理解）
    26.                 Backtrack(i+1);   //继续探索以第i层结点为根结点的子树
    27.                 Swap(x[i],x[j]);   //探索完要回溯时，只要做探索前的反“动作”就可以了
    28.             }
    29.            f-=f2[i];   //探索完要回溯时，只要做探索前的反“动作”就可以了
    30.            f1-=M[x[j]][1];   //探索完要回溯时，只要做探索前的反“动作”就可以了
    31.         }
    32.     }
    33. }

    会场安排问题（贪心）

    算法思想：

    只需要关心开始时间和结束时间，，只要集合里面的最大结束时间和当前的开始时间就可以

    算法描述：

     假设在足够多的会场里安排一批活动，并希望使用尽可能少的会场。设计一个有效的贪心算法进行安排。

     贪心策略：采用结束时间最早的会场作为贪心选择。

     2. 用数组 s ss 和 f ff 分别存储各活动的开始时间和结束时间。

    将数组 s ss 排序，该次序为各活动选择会场的次序。
    将数组 f ff 排序。由于会场的结束时间由活动的结束时间决定，排序后的数组也是会场的结束时间点。
     3. （1）先为最早开始的活动开辟一个会场，此时会场的最早结束时间为该活动的结束时间。（2）然后遍历剩下的活动。对于每个活动，判断当前最早结束的会场内是否仍有活动：如果有，开辟一个新会场；如果没有，说明当前最早结束的会场能容纳当前的活动，更新会场的结束时间点，保证最早结束的会场最先开始下一个活动。

    复杂度分析：

    时间复杂度：O(nlogn) 排序

    空间复杂度：O(n)

    正确性分析：

    代码：

    1. #include 
    2. #include 
    3. using namespace std;
    4. //5
    5. //1 23
    6. //12 28
    7. //25 35
    8. //27 80
    9. //36 50
    10. const int N = 1e5 + 10;
    11. int n;
    12. struct hd{
    13. 	int a, b;
    14. }h[N];
    15. bool cmp(hd h1, hd h2) {
    16. 	return h1.a < h2.a;
    17. }
    18. int main() {
    19. 	cin >> n;
    20. 	for(int i = 0; i < n; i ++ ) cin >> h[i].a >> h[i].b;
    21. 	
    22. 	sort(h, h + n, cmp);
    23. 	int res = -1;
    24. 	for(int i = 0; i < n; i ++ ) {
    25. 		int j = i + 1, t = 1;
    26. 		while(h[j].a < h[i].b && j < n) {
    27. 			t ++;
    28. 			j ++;
    29. 		}
    30. 		res = max(res, t);
    31. 	}
    32. 	cout << res << endl;
    33. 	return 0;
    34. }
    1. // 贪心正解：
    2. #include
    3. using namespace std;
    4. int main(){
    5. 	int n;
    6. 	cout<<"请输入活动的个数："<
    7. 	cin>>n;
    8. 	
    9. 	int s[n],f[n];
    10. 	cout<<"请输入每个活动的开始时间和结束时间："<
    11. 	for(int i=0;i
    12. 	{
    13. 		cin>>s[i]>>f[i];
    14. 	}
    15. 	
    16. 	sort(s,s+n);//理解一下为什么都要升序 
    17. 	sort(f,f+n);
    18. 	
    19. 	//会场的最短结束时间次序用j来表示，待分配的活动按i来遍历 
    20. 	int j=0,ans=0;
    21. 	
    22. 	for(int i=0;i
    23. 	{
    24. 		if(s[i] < f[j])
    25. 		{
    26. 			ans++;
    27. 		}
    28. 		else
    29. 		{
    30. 			j++;
    31. 		}
    32. 	} 
    33.      
    34. 	cout<<"最小会场数是："<
    35. 	return 0;
    36. }

    图m着色问题（回溯法）

    算法思想：

    算法尝试所有可能的染色方案，并使用剪枝操作减少无效搜索，最终输出染色方案的数量。

    算法描述：

    设图G=(V, E), |V|=n, 颜色数= m, 用邻接矩阵a表示G, 用整数1, 2…m来表示

    m种不同的颜色。顶点i所着的颜色用x[i]表示。

    问题的解向量可以表示为n元组x={ x[1],…,x[n] }. x[i]∈{1,2,…,m},

    解空间树为排序树,是一棵n+1层的完全m叉树.

    在解空间树中做深度优先搜索, 约束条件:如果g[j][i]=1 , x[i] ≠ x[j]

    复杂度分析：

    • 时间复杂度：O(m^n)
    • 空间复杂度：O(N^2)

    正确性分析：

    代码：

    一颗排列树，一般时间为O(n!)

    1. #include 
    2. using namespace std;
    3.  
    4. const int N = 1e4 + 10;
    5. int m, n, edgenum;
    6. int x[N], g[N][N];
    7. int ans;
    8.  
    9. int check(int i) {
    10. 	for(int j = 1; j < i; j ++ ) {
    11. 		if(g[i][j] && x[i] == x[j]) return false;
    12. 	}
    13. 	return true;
    14. }
    15.  
    16. void dfs(int u) {
    17. 	if(u > n) {
    18. 		ans ++;
    19. 		for(int i = 1; i <= n; i ++ ) {
    20. 			cout << x[i] << ' ';
    21. 		}
    22. 		cout << endl;
    23. 		return ;
    24. 	}
    25. 	else {
    26. 		for(int i = 0; i < m; i ++ ) {
    27. 			x[u] = i;
    28. 			if(check(u))
    29. 				dfs(u + 1);
    30. 			x[u] = 0;
    31. 		}
    32. 	}
    33. }
    34.  
    35. int main() {
    36. 	cin >> n >> m >> edgenum;
    37. 	for(int i = 0; i < edgenum; i ++ ) {
    38. 		int a, b;
    39. 		cin >> a >> b;
    40. 		g[a][b] = g[b][a] = 1;
    41. 	}
    42. 	
    43. 	dfs(1);
    44. 	if(ans) 
    45. 		cout << "染色方案的数量为:" << ans << endl;
    46. 	else cout << "无染色方案" << endl; 
    47. 	return 0;
    48. }
    49.  
    50. // 优化
    51. #include 
    52. #include 
    53. using namespace std;
    54.  
    55. const int N = 1e4 + 10;
    56. int m, n, edgenum;
    57. int x[N];
    58. vector<int> g[N];
    59. int ans;
    60.  
    61. bool check(int i) {
    62.     for (int j : g[i]) {
    63.         if (x[i] == x[j]) return false;
    64.     }
    65.     return true;
    66. }
    67.  
    68. void dfs(int u) {
    69.     if (u > n) {
    70.         ans++;
    71.         for (int i = 1; i <= n; i++) {
    72.             cout << x[i] << ' ';
    73.         }
    74.         cout << endl;
    75.         return;
    76.     }
    77.  
    78.     for (int i = 0; i < m; i++) {
    79.         x[u] = i;
    80.         if (check(u)) {
    81.             dfs(u + 1);
    82.         }
    83.         x[u] = -1;  // 重置状态
    84.     }
    85. }
    86.  
    87. int main() {
    88.     cin >> n >> m >> edgenum;
    89.     for (int i = 0; i < edgenum; i++) {
    90.         int a, b;
    91.         cin >> a >> b;
    92.         g[a].push_back(b);
    93.         g[b].push_back(a);
    94.     }
    95.  
    96.     fill(x, x + N, -1);  // 初始化颜色数组为-1
    97.  
    98.     dfs(1);
    99.     if (ans)
    100.         cout << "染色方案的数量为:" << ans << endl;
    101.     else
    102.         cout << "无染色方案" << endl;
    103.     return 0;
    104. }

    旅行售货员问题tsp（回溯法）

    算法思想：

    它通过递归搜索所有可能的路径，并在每一步进行剪枝（分支限界）来减少不必要的计算，尝试找到最短的环路。其实就是寻找哈密尔顿回路

    算法描述：

    1. 递归终止条件：当 u == citynum 时，表示已经访问所有城市，此时需要检查是否可以回到起点并更新最优成本。
    2. 循环和交换：在每一步中，尝试将当前步的节点与后续节点进行交换以生成不同的路径。
    3. 剪枝条件：如果当前路径的成本加上从前一个城市到当前城市的成本小于当前已知的最优成本，则继续搜索。

    复杂度分析：

    • 时间复杂度: ( O(n!) )
    • 空间复杂度: ( O(n) )

    正确性分析：

    代码：

    同样是一个排序树

    1. void BackTrack(int u) { // u指的是第u步 
    2. 	if(u == citynum) { // 此时是叶子结点的父节点 
    3. 		if(Graph[x[u - 1]][x[u]] != NoEdge && Graph[x[u]][1] != NoEdge && (Graph[x[u - 1]][x[u]] + Graph[x[u]][1] + currentcost < bestcost || bestcost == max_)) {
    4. 			bestcost = Graph[x[u - 1]][x[u]] + Graph[x[u]][1] + currentcost;
    5. 			for(int i = 1; i <= citynum; i ++ ) {
    6. 				bestx[i] = x[i];
    7. 			}
    8. 		}
    9. 		return;
    10. 	}
    11. 	else {
    12. 		for(int j = u; j <= citynum; j ++ ) {
    13. 			if(Graph[x[u - 1]][x[j]] != NoEdge && Graph[x[u - 1]][x[j]] + currentcost < bestcost || bestcost == max_) { // 分支和界限 
    14. 				swap(x[u], x[j]);
    15. 				currentcost += Graph[x[u - 1]][x[u]];
    16. 				BackTrack(u + 1);
    17. 				currentcost -= Graph[x[u - 1]][x[u]];
    18. 				swap(x[u], x[j]);
    19. 			}
    20. 		}
    21. 	}
    22. }

    N皇后问题（回溯法）

    算法思想：

    任意两个皇后都不能处于同一行、同一列或同一斜线上。可以把八皇后问题扩展到n皇后问题，即在n×n的棋盘上摆放n个皇后，使任意两个皇后都不能处于同一行、同一列或同一斜线上。 

    算法描述：

    回溯法，解空间树是一个排序树

    复杂度分析：

    时间复杂度O(n!)

    空间复杂度O(n^2)

    正确性分析：

    代码：dg主对角线，+n防止负值，udg副对角线不会有负值

    1. #include 
    2. using namespace std;
    3.  
    4. const int N = 1010;
    5. int n, ans;
    6. int g[N][N];
    7. int col[N], dg[N], udg[N];
    8.  
    9. void dfs(int u) {
    10.     if(u > n) {
    11.         ans ++;
    12.         for(int i = 1; i <= n ; i++ ) {
    13.             for(int j = 1; j <= n; j ++ ) {
    14.                 if(g[i][j]) {
    15.                     cout << "q ";
    16.                 }
    17.                 else cout << ". ";
    18.             }
    19.             cout << endl;
    20.         }
    21.         cout << endl;
    22.         return ;
    23.     }
    24.     else {
    25.         for(int i = 1; i <= n; i ++ ) {
    26.             if(!col[i] && !dg[i - u + n] && !udg[i + u]) {
    27.                 col[i] = 1;
    28.                 dg[i - u + n] = 1;
    29.                 udg[i + u] = 1;
    30.                 g[u][i] = 1;
    31.                 dfs(u + 1);
    32.                 g[u][i] = 0;
    33.                 col[i] = 0;
    34.                 dg[i - u + n] = 0;
    35.                 udg[i + u] = 0;
    36.             }
    37.         }
    38.     }
    39. }
    40.  
    41. int main() {
    42.     cin >> n;
    43.  
    44.     dfs(1);
    45.     cout << ans << endl;
    46.     return 0;
    47. }

    KMP算法（字符串）

    算法思想：

    找出模式串在文本串中的出现位置，暴力解法两个循环O(mn)

    kmp算法,不用在文本串中回溯了。空间复杂度O(n),时间复杂度O(m+n)

    算法描述：

    复杂度分析：

    正确性分析：

    代码：

    1. #include 
    2.  
    3. using namespace std;
    4.  
    5. const int N = 100010, M = 10010; //N为模式串长度，M匹配串长度
    6.  
    7. int n, m;
    8. int ne[M];
    9. char s[N], p[M];  //s为模式串， p为匹配串
    10.  
    11. int main()
    12. {
    13.     cin >> n >> s+1 >> m >> p+1;  //下标从1开始
    14.  
    15.     //求next[]数组
    16.     for(int i = 2, j = 0; i <= m; i++)
    17.     {
    18.         while(j && p[i] != p[j+1]) j = ne[j];
    19.         if(p[i] == p[j+1]) j++;
    20.         ne[i] = j;
    21.     }
    22.     //匹配操作
    23.     for(int i = 1, j = 0; i <= n; i++)
    24.     {
    25.         while(j && s[i] != p[j+1]) j = ne[j]; // 回溯
    26.         if(s[i] == p[j+1]) j++;
    27.         if(j == m)  // 满足匹配条件，打印开头下标, 从0开始
    28.         {
    29.             //匹配完成后的具体操作
    30.             //如：输出以0开始的匹配子串的首字母下标
    31.             //printf("%d ", i - m); (若从1开始，加1)
    32.             j = ne[j];            //再次继续匹配
    33.         }
    34.     }
    35.  
    36.     return 0;
    37. }

  • 相关阅读:
    MATLAB中subplot函数的使用
    【算法与数据结构】--目录
    Springboot毕设项目鲜花售卖管理系统593y6java+VUE+Mybatis+Maven+Mysql+sprnig）
    [CCS][sysconfig] 图形化工具的使用说明
    吃透Chisel语言.37.Chisel实战之以FIFO为例（二）——基于FIFO的串口通信：串口发送“Hello World!”
    手动写编译器实现加减乘除运算
    Git_GitHub——基本操作、创建远程库、远程库操作、团队协作、SSH免密登录
    Git笔记简化版
    你的Edge浏览器难道不需要一个好看的浏览器起始页嘛
    logrotate日志轮转
  • 原文地址：https://blog.csdn.net/qq_74593128/article/details/139683511