常用算法C语言描述，实用案例与核心技巧？

目录

1. 排序算法

   • 1 冒泡排序
   • 2 选择排序
   • 3 插入排序
   • 4 快速排序
   • 5 归并排序
   • 6 希尔排序
   • 7 堆排序

2. 查找算法

   • 1 顺序查找
   • 2 二分查找

3. 图论算法

   • 1 深度优先搜索
   • 2 广度优先搜索
   • 3 Dijkstra 最短路径算法
   • 4 Floyd-Warshall 最短路径算法
   • 5 最小生成树 - Kruskal 算法
   • 6 最小生成树 - Prim 算法

4. 动态规划

   • 1 斐波那契数列
   • 2 0/1 背包问题
   • 3 最长公共子序列

5. 字符串算法

   • 1 KMP 算法
   • 2 字符串匹配 - BF 算法

6. 其他经典算法

   • 1 分治法 - 求解最近点对
   • 2 贪心算法 - 活动选择问题
   • 3 回溯法 - N皇后问题

使用说明

• 代码风格：所有代码均采用标准 C 语言编写，注重可读性和注释。
• 数据结构：主要使用数组来存储数据，对于图，使用邻接矩阵和邻接表两种方式。
• 编译运行：将代码片段整合到 .c 文件中，使用 C 编译器（如 GCC）编译并运行。
• 辅助函数：为了简化主函数，一些算法会使用辅助函数（如交换函数 swap、打印数组函数 printArray），这些函数在示例中会一并给出。

排序算法

1 冒泡排序

• 思路：重复遍历要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来，遍历数列的工作是重复地进行，直到没有再需要交换的元素为止。
• 复杂度：
  • 时间：最好 O(n)，平均 O(n²)，最坏 O(n²)
  • 空间：O(1)
• 特点：稳定，简单但效率低。

#include <stdio.h>
void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}
void bubbleSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        // 每次遍历后，最大的元素会“冒泡”到末尾
        // 所以内层循环可以减少一次
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                swap(&arr[j], &arr[j + 1]);
            }
        }
    }
}
void printArray(int arr[], int size) {
    for (int i = 0; i < size; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}
int main() {
    int arr[] = {64, 34, 25, 12, 22, 11, 90};
    int n = sizeof(arr) / sizeof(arr[0]);
    printf("Original array: \n");
    printArray(arr, n);
    bubbleSort(arr, n);
    printf("Sorted array: \n");
    printArray(arr, n);
    return 0;
}

2 选择排序

• 思路：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
• 复杂度：
  • 时间：最好 O(n²)，平均 O(n²)，最坏 O(n²)
  • 空间：O(1)
• 特点：不稳定，交换次数少。

// swap 函数同上
void selectionSort(int arr[], int n) {
    int i, j, min_idx;
    for (i = 0; i < n - 1; i++) {
        // 找到未排序部分的最小元素索引
        min_idx = i;
        for (j = i + 1; j < n; j++) {
            if (arr[j] < arr[min_idx]) {
                min_idx = j;
            }
        }
        // 将找到的最小元素与未排序部分的第一个元素交换
        if (min_idx != i) {
            swap(&arr[min_idx], &arr[i]);
        }
    }
}
// printArray 函数同上
// main 函数中调用 selectionSort

3 插入排序

• 思路：通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
• 复杂度：
  • 时间：最好 O(n)，平均 O(n²)，最坏 O(n²)
  • 空间：O(1)
• 特点：稳定，对于小规模或基本有序的数据效率高。

// swap 函数同上
void insertionSort(int arr[], int n) {
    int i, key, j;
    for (i = 1; i < n; i++) {
        key = arr[i]; // 当前要插入的元素
        j = i - 1;
        // 将大于 key 的元素向后移动
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        arr[j + 1] = key; // 插入 key 到正确位置
    }
}
// printArray 函数同上
// main 函数中调用 insertionSort

4 快速排序

• 思路：采用分治法策略，选择一个基准元素，将数组分为两部分，一部分小于基准，一部分大于基准，然后递归地对这两部分进行排序。
• 复杂度：
  • 时间：最好 O(n log n)，平均 O(n log n)，最坏 O(n²) (当数组已经有序或逆序时)
  • 空间：O(log n) (递归栈空间)
• 特点：不稳定，平均性能非常好，是应用最广泛的排序算法之一。

// swap 函数同上
int partition(int arr[], int low, int high) {
    int pivot = arr[high]; // 选择最后一个元素作为基准
    int i = (low - 1);     // 小于基准的元素的索引
    for (int j = low; j <= high - 1; j++) {
        // 如果当前元素小于或等于基准
        if (arr[j] <= pivot) {
            i++; // 增加小于基准的元素的索引
            swap(&arr[i], &arr[j]);
        }
    }
    swap(&arr[i + 1], &arr[high]);
    return (i + 1);
}
void quickSort(int arr[], int low, int high) {
    if (low < high) {
        // pi 是分区后基准的位置
        int pi = partition(arr, low, high);
        // 递归地对基准左右两部分进行排序
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}
// printArray 函数同上
// main 函数中调用 quickSort(arr, 0, n - 1);

5 归并排序

• 思路：采用分治法策略，将数组分成两半，分别排序，然后将两个有序的数组合并成一个有序的数组。
• 复杂度：
  • 时间：最好 O(n log n)，平均 O(n log n)，最坏 O(n log n)
  • 空间：O(n) (需要额外的临时数组)
• 特点：稳定，时间复杂度稳定，适合大数据量的排序。

void merge(int arr[], int l, int m, int r) {
    int i, j, k;
    int n1 = m - l + 1;
    int n2 = r - m;
    // 创建临时数组
    int L[n1], R[n2];
    // 拷贝数据到临时数组
    for (i = 0; i < n1; i++)
        L[i] = arr[l + i];
    for (j = 0; j < n2; j++)
        R[j] = arr[m + 1 + j];
    // 合并临时数组
    i = 0;
    j = 0;
    k = l;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        } else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }
    // 拷贝剩余元素
    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }
    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }
}
void mergeSort(int arr[], int l, int r) {
    if (l < r) {
        int m = l + (r - l) / 2;
        // 递归排序左右两部分
        mergeSort(arr, l, m);
        mergeSort(arr, m + 1, r);
        // 合并
        merge(arr, l, m, r);
    }
}
// printArray 函数同上
// main 函数中调用 mergeSort(arr, 0, n - 1);

6 希尔排序

• 思路：是插入排序的改进版，通过将数组分成多个子序列，对每个子序列进行插入排序，逐渐减少子序列的长度，直到最后整个序列基本有序，再进行一次直接插入排序。
• 复杂度：
  • 时间：与增量序列有关，通常在 O(n log n) 和 O(n²) 之间
  • 空间：O(1)
• 特点：不稳定，是第一个突破 O(n²) 的排序算法。

// swap 函数同上
void shellSort(int arr[], int n) {
    for (int gap = n / 2; gap > 0; gap /= 2) {
        // 对每个 gap 进行插入排序
        for (int i = gap; i < n; i++) {
            int temp = arr[i];
            int j;
            for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) {
                arr[j] = arr[j - gap];
            }
            arr[j] = temp;
        }
    }
}
// printArray 函数同上
// main 函数中调用 shellSort

7 堆排序

• 思路：利用堆这种数据结构设计的一种排序算法，首先将待排序序列构造成一个大顶堆，整个序列的最大值就是堆顶的根节点，将其与末尾元素进行交换，此时末尾就为最大值，然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值，如此反复执行，便能得到一个有序序列。
• 复杂度：
  • 时间：最好 O(n log n)，平均 O(n log n)，最坏 O(n log n)
  • 空间：O(1)
• 特点：不稳定，原地排序，不需要额外空间。

// swap 函数同上
// 调整堆，使其满足大顶堆性质
void heapify(int arr[], int n, int i) {
    int largest = i;        // 初始化最大值为根
    int left = 2 * i + 1;   // 左子节点
    int right = 2 * i + 2;  // 右子节点
    if (left < n && arr[left] > arr[largest])
        largest = left;
    if (right < n && arr[right] > arr[largest])
        largest = right;
    // 如果最大值不是根，交换并继续调整受影响的子树
    if (largest != i) {
        swap(&arr[i], &arr[largest]);
        heapify(arr, n, largest);
    }
}
void heapSort(int arr[], int n) {
    // 构建初始大顶堆 (从最后一个非叶子节点开始)
    for (int i = n / 2 - 1; i >= 0; i--)
        heapify(arr, n, i);
    // 逐个从堆顶取出元素
    for (int i = n - 1; i > 0; i--) {
        swap(&arr[0], &arr[i]); // 将当前最大值移到数组末尾
        heapify(arr, i, 0);     // 对剩余元素重新调整堆
    }
}
// printArray 函数同上
// main 函数中调用 heapSort

查找算法

1 顺序查找

• 思路：从数据结构的一端开始，逐个检查每个元素，直到找到所需的元素或检查完所有元素。
• 复杂度：
  • 时间：最好 O(1)，平均 O(n)，最坏 O(n)
  • 空间：O(1)
• 特点：实现简单，适用于无序数据。

int linearSearch(int arr[], int n, int x) {
    for (int i = 0; i < n; i++) {
        if (arr[i] == x) {
            return i; // 返回找到元素的索引
        }
    }
    return -1; // 未找到
}
// main 函数中调用
// int index = linearSearch(arr, n, 22);
// if (index != -1) printf("Element found at index %d\n", index);

2 二分查找

• 思路：在有序数组中，将数组中间位置的元素与查找值比较，如果中间元素正好是要查找的元素，则查找过程结束；如果某一特定元素大于或小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且和比较过中间元素的那一半不重复比较。
• 复杂度：
  • 时间：最好 O(1)，平均 O(log n)，最坏 O(log n)
  • 空间：O(1)
• 特点：效率高，但要求数据必须有序。

int binarySearch(int arr[], int l, int r, int x) {
    while (l <= r) {
        int mid = l + (r - l) / 2;
        // 检查 x 是否在中间
        if (arr[mid] == x) {
            return mid;
        }
        // x 更大，则它只能在右半部分
        if (arr[mid] < x) {
            l = mid + 1;
        }
        // x 更小，则它只能在左半部分
        else {
            r = mid - 1;
        }
    }
    return -1; // 未找到
}
// main 函数中调用 (确保数组已排序)
// int index = binarySearch(arr, 0, n - 1, 22);

图论算法

1 深度优先搜索

• 思路：从起始顶点开始，沿着一条路径一直走到底，直到不能再前进为止，然后回溯到上一个节点，选择另一条路径继续探索，直到所有节点都被访问。
• 实现：通常使用递归或栈。

#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTICES 100
// 邻接表表示的图
struct Graph {
    int numVertices;
    struct Node* adjLists[MAX_VERTICES];
};
// 邻接表中的节点
struct Node {
    int vertex;
    struct Node* next;
};
// 创建节点
struct Node* createNode(int v) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->vertex = v;
    newNode->next = NULL;
    return newNode;
}
// 创建图
struct Graph* createGraph(int vertices) {
    struct Graph* graph = (struct Graph*)malloc(sizeof(struct Graph));
    graph->numVertices = vertices;
    for (int i = 0; i < vertices; i++) {
        graph->adjLists[i] = NULL;
    }
    return graph;
}
// 添加边
void addEdge(struct Graph* graph, int src, int dest) {
    // 添加从 src 到 dest 的边
    struct Node* newNode = createNode(dest);
    newNode->next = graph->adjLists[src];
    graph->adjLists[src] = newNode;
    // 无向图，添加反向边
    newNode = createNode(src);
    newNode->next = graph->adjLists[dest];
    graph->adjLists[dest] = newNode;
}
// DFS 辅助函数 (递归)
void DFSUtil(struct Graph* graph, int vertex, int visited[]) {
    visited[vertex] = 1;
    printf("Visited %d\n", vertex);
    struct Node* adjList = graph->adjLists[vertex];
    struct Node* temp = adjList;
    while (temp != NULL) {
        int adjVertex = temp->vertex;
        if (visited[adjVertex] == 0) {
            DFSUtil(graph, adjVertex, visited);
        }
        temp = temp->next;
    }
}
// DFS 主函数
void DFS(struct Graph* graph, int startVertex) {
    int visited[MAX_VERTICES];
    for (int i = 0; i < graph->numVertices; i++) {
        visited[i] = 0;
    }
    DFSUtil(graph, startVertex, visited);
}
// main 函数中调用
// struct Graph* graph = createGraph(4);
// addEdge(graph, 0, 1);
// addEdge(graph, 0, 2);
// addEdge(graph, 1, 2);
// addEdge(graph, 2, 3);
// DFS(graph, 0);

2 广度优先搜索

• 思路：从起始顶点开始，先访问其所有直接邻居，然后再访问这些邻居的邻居，一层一层向外扩展。
• 实现：通常使用队列。

#include <stdio.h>
#include <stdlib.h>
// 需要上面的 Graph 和 Node 结构体定义
// 需要上面的 createGraph, addEdge 函数
// BFS 实现
void BFS(struct Graph* graph, int startVertex) {
    int visited[MAX_VERTICES] = {0};
    struct Node* queue[MAX_VERTICES];
    int front = -1, rear = -1;
    visited[startVertex] = 1;
    queue[++rear] = createNode(startVertex); // 将起始节点入队
    printf("BFS starting from vertex %d:\n", startVertex);
    while (front != rear) {
        struct Node* current = queue[++front];
        int currentVertex = current->vertex;
        printf("Visited %d\n", currentVertex);
        struct Node* temp = graph->adjLists[currentVertex];
        while (temp != NULL) {
            int adjVertex = temp->vertex;
            if (visited[adjVertex] == 0) {
                visited[adjVertex] = 1;
                queue[++rear] = createNode(adjVertex);
            }
            temp = temp->next;
        }
    }
}
// main 函数中调用
// struct Graph* graph = createGraph(4);
// addEdge(graph, 0, 1);
// addEdge(graph, 0, 2);
// addEdge(graph, 1, 2);
// addEdge(graph, 2, 3);
// BFS(graph, 0);

3 Dijkstra 最短路径算法

• 思路：计算从一个源点到图中所有其他顶点的最短路径，它使用贪心策略，每次都选择当前距离源点最近的未访问顶点进行松弛操作。
• 实现：使用优先队列（通常用数组模拟）来存储顶点及其距离。

#include <limits.h>
#include <stdbool.h>
#define V 9 // 顶点数量
int minDistance(int dist[], bool sptSet[]) {
    int min = INT_MAX, min_index;
    for (int v = 0; v < V; v++) {
        if (sptSet[v] == false && dist[v] <= min) {
            min = dist[v];
            min_index = v;
        }
    }
    return min_index;
}
void printSolution(int dist[]) {
    printf("Vertex \t\t Distance from Source\n");
    for (int i = 0; i < V; i++) {
        printf("%d \t\t %d\n", i, dist[i]);
    }
}
void dijkstra(int graph[V][V], int src) {
    int dist[V];     // 存储从 src 到 i 的最短距离
    bool sptSet[V]; // sptSet[i] 为 true 如果顶点 i 在最短路径树中
    for (int i = 0; i < V; i++) {
        dist[i] = INT_MAX;
        sptSet[i] = false;
    }
    dist[src] = 0;
    for (int count = 0; count < V - 1; count++) {
        int u = minDistance(dist, sptSet);
        sptSet[u] = true;
        for (int v = 0; v < V; v++) {
            if (!sptSet[v] && graph[u][v] && dist[u] != INT_MAX && dist[u] + graph[u][v] < dist[v]) {
                dist[v] = dist[u] + graph[u][v];
            }
        }
    }
    printSolution(dist);
}
// main 函数中调用
// int graph[V][V] = {{0, 4, 0, 0, 0, 0, 0, 8, 0},
//                    {4, 0, 8, 0, 0, 0, 0, 11, 0},
//                    {0, 8, 0, 7, 0, 4, 0, 0, 2},
//                    {0, 0, 7, 0, 9, 14, 0, 0, 0},
//                    {0, 0, 0, 9, 0, 10, 0, 0, 0},
//                    {0, 0, 4, 14, 10, 0, 2, 0, 0},
//                    {0, 0, 0, 0, 0, 2, 0, 1, 6},
//                    {8, 11, 0, 0, 0, 0, 1, 0, 7},
//                    {0, 0, 2, 0, 0, 0, 6, 7, 0}};
// dijkstra(graph, 0);

4 Floyd-Warshall 最短路径算法

• 思路：用于寻找图中所有顶点对之间的最短路径，它使用动态规划，通过考虑每个顶点作为中间点来逐步更新最短路径。
• 实现：使用邻接矩阵。

// 需要上面的 V 宏定义
void floydWarshall(int graph[V][V]) {
    int dist[V][V], i, j, k;
    for (i = 0; i < V; i++) {
        for (j = 0; j < V; j++) {
            dist[i][j] = graph[i][j];
        }
    }
    for (k = 0; k < V; k++) {
        for (i = 0; i < V; i++) {
            for (j = 0; j < V; j++) {
                if (dist[i][k] + dist[k][j] < dist[i][j]) {
                    dist[i][j] = dist[i][k] + dist[k][j];
                }
            }
        }
    }
    printf("Following matrix shows the shortest distances between every pair of vertices \n");
    for (i = 0; i < V; i++) {
        for (j = 0; j < V; j++) {
            if (dist[i][j] == INT_MAX)
                printf("%7s", "INF");
            else
                printf("%7d", dist[i][j]);
        }
        printf("\n");
    }
}
// main 函数中调用 (与 Dijkstra 相同的图)

5 最小生成树 - Kruskal 算法

• 思路：按边的权重从小到大排序，依次选择边，如果这条边连接的两个顶点不在同一个集合中，则将其加入最小生成树，并合并这两个顶点的集合。
• 实现：使用并查集数据结构来高效管理集合。

#include <stdio.h>
#include <stdlib.h>
// 边的结构体
struct Edge {
    int src, dest, weight;
};
// 子集的结构体，用于并查集
struct Subset {
    int parent;
    int rank;
};
// 比较函数，用于 qsort
int compare(const void* a, const void* b) {
    struct Edge* a1 = (struct Edge*)a;
    struct Edge* b1 = (struct Edge*)b;
    return a1->weight > b1->weight;
}
// 并查集的查找操作 (路径压缩)
int find(struct subsets subsets[], int i) {
    if (subsets[i].parent != i) {
        subsets[i].parent = find(subsets, subsets[i].parent);
    }
    return subsets[i].parent;
}
// 并查集的合并操作 (按秩合并)
void Union(struct subsets subsets[], int x, int y) {
    int xroot = find(subsets, x);
    int yroot = find(subsets, y);
    if (subsets[xroot].rank < subsets[yroot].rank) {
        subsets[xroot].parent = yroot;
    } else if (subsets[xroot].rank > subsets[yroot].rank) {
        subsets[yroot].parent = xroot;
    } else {
        subsets[yroot].parent = xroot;
        subsets[xroot].rank++;
    }
}
// Kruskal 算法主函数
void KruskalMST(struct Edge edges[], int E, int V) {
    struct Edge result[V]; // 存储 MST 的结果
    struct subsets* subsets = (struct subsets*)malloc(V * sizeof(struct subsets));
    int e = 0; // 用于 result 的索引
    int i = 0; // 用于 edges 的索引
    // 初始化子集
    for (int v = 0; v < V; v++) {
        subsets[v].parent = v;
        subsets[v].rank = 0;
    }
    // 按权重对边进行排序
    qsort(edges, E, sizeof(edges[0]), compare);
    // 遍历排序后的边
    while (e < V - 1 && i < E) {
        struct Edge next_edge = edges[i++];
        int x = find(subsets, next_edge.src);
        int y = find(subsets, next_edge.dest);
        if (x != y) {
            result[e++] = next_edge;
            Union(subsets, x, y);
        }
    }
    // 打印 MST
    printf("Following are the edges in the constructed MST\n");
    for (i = 0; i < e; ++i) {
        printf("%d -- %d == %d\n", result[i].src, result[i].dest, result[i].weight);
    }
    free(subsets);
}
// main 函数中调用
// int V = 4; // 顶点数
// int E = 5; // 边数
// struct Edge edges[] = {{0, 1, 10}, {0, 2, 6}, {0, 3, 5}, {1, 3, 15}, {2, 3, 4}};
// KruskalMST(edges, E, V);

6 最小生成树 - Prim 算法

• 思路：从一个顶点开始，不断选择与当前生成树连接的权重最小的边，直到所有顶点都被包含进来。
• 实现：使用优先队列。

// 需要上面的 V 宏定义
// 辅助函数，用于在 key 数组中找到最小值的顶点
int minKey(int key[], bool mstSet[]) {
    int min = INT_MAX, min_index;
    for (int v = 0; v < V; v++) {
        if (mstSet[v] == false && key[v] < min) {
            min = key[v];
            min_index = v;
        }
    }
    return min_index;
}
// Prim 算法主函数
void primMST(int graph[V][V]) {
    int parent[V];   // 存储构建的 MST
    int key[V];      // 存储连接到 MST 的最小权重边
    bool mstSet[V]; // 集合 mstSet[] 表示顶点 i 是否在 MST 中
    for (int i = 0; i < V; i++) {
        key[i] = INT_MAX;
        mstSet[i] = false;
    }
    key[0] = 0;     // 第一个顶点作为起点
    parent[0] = -1; // 第一个顶点是 MST 的根
    for (int count = 0; count < V - 1; count++) {
        int u = minKey(key, mstSet);
        mstSet[u] = true;
        for (int v = 0; v < V; v++) {
            if (graph[u][v] && mstSet[v] == false && graph[u][v] < key[v]) {
                parent[v] = u;
                key[v] = graph[u][v];
            }
        }
    }
    // 打印 MST
    printf("Edge \tWeight\n");
    for (int i = 1; i < V; i++) {
        printf("%d - %d \t%d \n", parent[i], i, graph[i][parent[i]]);
    }
}
// main 函数中调用 (与 Dijkstra 相同的图)

动态规划

1 斐波那契数列

• 思路：斐波那契数列 F(n) = F(n-1) + F(n-2)，直接递归会有大量重复计算，动态规划通过存储已计算的结果来避免重复计算。
• 实现：自底向上迭代。

// 带备忘录的递归 (自顶向下)
long long fibMemo(int n, long long memo[]) {
    if (n <= 1) return n;
    if (memo[n] != 0) return memo[n];
    memo[n] = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
    return memo[n];
}
// 迭代法 (自底向上)
long long fibDP(int n) {
    if (n <= 1) return n;
    long long a = 0, b = 1, c;
    for (int i = 2; i <= n; i++) {
        c = a + b;
        a = b;
        b = c;
    }
    return b;
}
// main 函数中调用
// int n = 50;
// long long memo[n+1];
// memset(memo, 0, sizeof(memo));
// printf("Fibonacci of %d is %lld\n", n, fibMemo(n, memo));
// printf("Fibonacci of %d is %lld\n", n, fibDP(n));

2 0/1 背包问题

• 思路：给定一组物品，每种物品都有自己的重量和价值，在限定的总重量内，如何选择才能使物品的总价值最高，每个物品只能选一次或不选。
• 实现：使用二维 DP 表 dp[i][w] 表示考虑前 i 个物品，背包容量为 w 时的最大价值。

int knapSack(int W, int wt[], int val[], int n) {
    int dp[n + 1][W + 1];
    for (int i = 0; i <= n; i++) {
        for (int w = 0; w <= W; w++) {
            if (i == 0 || w == 0) {
                dp[i][w] = 0;
            } else if (wt[i - 1] <= w) {
                dp[i][w] = (val[i - 1] + dp[i - 1][w - wt[i - 1]]) > (dp[i - 1][w]) ? 
                           (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];
}
// main 函数中调用
// int val[] = {60, 100, 120};
// int wt[] = {10, 20, 30};
// int W = 50;
// int n = sizeof(val) / sizeof(val[0]);
// printf("Maximum value that can be obtained is %d\n", knapSack(W, wt, val, n));

3 最长公共子序列

• 思路：找出两个字符串中最长的子序列，这个子序列不一定是连续的。
• 实现：使用二维 DP 表 dp[i][j] 表示字符串 str1[0...i-1] 和 str2[0...j-1] 的 LCS 长度。

void printLCS(char *X, char *Y, int m, int n) {
    int L[m + 1][n + 1];
    for (int i = 0; i <= m; i++) {
        for (int j = 0; j <= n; j++) {
            if (i == 0 || j == 0) {
                L[i][j] = 0;
            } else if (X[i - 1] == Y[j - 1]) {
                L[i][j] = L[i - 1][j - 1] + 1;
            } else {
                L[i][j] = (L[i - 1][j] > L[i][j - 1]) ? L[i - 1][j] : L[i][j - 1];
            }
        }
    }
    int index = L[m][n];
    char lcs[index + 1];
    lcs[index] = '\0';