1、分治法(Divide and Conquer)
思想:将问题分解为若干个子问题,递归地解决子问题,然后将子问题的解 合并 起来得到原问题的解。
经典问题:归并排序(Merge Sort)
cue: 如何将一个无序数组排序?归并排序通过递归地将数组划分为更小的子数组,对子数组进行排序,然后将已排序的子数组合并成一个大的有序数组。
#include <stdio.h>
// 合并两个有序数组
void merge(int arr[], int left[], int size_left, int right[], int size_right, int merged[]) {
int i = 0, j = 0, k = 0;
// 遍历两个数组,将较小的元素放入merged数组中
while (i < size_left && j < size_right) {
if (left[i] <= right[j]) {
merged[k++] = left[i++];
} else {
merged[k++] = right[j++];
}
}
// 如果有剩余的元素,将它们添加到merged数组的末尾
while (i < size_left) {
merged[k++] = left[i++];
}
while (j < size_right) {
merged[k++] = right[j++];
}
}
// 归并排序的主要函数
void mergeSort(int arr[], int size) {
if (size < 2) {
return; // 数组只有一个或零个元素时,已经是有序的
}
// 找到中点,将数组分成两半
int mid = size / 2;
// 声明两个新数组,用于存储分割后的数组
int left[mid];
int right[size - mid];
// 复制数据到两个新数组
for (int i = 0; i < mid; i++) {
left[i] = arr[i];
}
for (int i = mid; i < size; i++) {
right[i - mid] = arr[i];
}
// 对两个新数组进行递归排序
mergeSort(left, mid);
mergeSort(right, size - mid);
// 合并两个已排序的数组
int merged[size];
merge(arr, left, mid, right, size - mid, merged);
// 将合并后的数组复制回原数组
for (int i = 0; i < size; i++) {
arr[i] = merged[i];
}
}
// 测试归并排序函数
int main() {
int arr[] = {12, 11, 13, 5, 6, 7};
int size = sizeof(arr) / sizeof(arr[0]);
printf("Original array: \n");
for (int i = 0; i < size; i++) {
printf("%d ", arr[i]);
}
mergeSort(arr, size);
printf("\nSorted array: \n");
for (int i = 0; i < size; i++) {
printf("%d ", arr[i]);
}
return 0;
}
2、动态规划(Dynamic Programming)
思想:将问题分解为若干个子问题, 保存 子问题的解以避免重复计算,并利用子问题的解来构建原问题的解。
经典问题:背包问题(Knapsack Problem)
cue: 给定一组物品,每个物品都有自己的重量和价值,以及一个背包的最大承重。如何选择物品放入背包,使得背包内物品的总价值最大,同时不超过背包的承重?
#include <stdio.h>
#include <stdlib.h>
#define MAX_N 100 // 假设物品的最大数量为100
#define MAX_W 1000 // 假设背包的最大容量为1000
int max(int a, int b) {
return a > b ? a : b;
}
// 0-1背包问题的动态规划解法
int knapsack_01(int W, int n, int weights[], int values[]) {
int dp[MAX_W + 1]; // dp[i]表示容量为i的背包能装下的最大价值
for (int i = 0; i <= W; i++) {
dp[i] = 0; // 初始化dp数组
}
for (int i = 1; i <= n; i++) { // 遍历每个物品
for (int w = W; w >= weights[i - 1]; w--) { // 遍历每个背包容量
dp[w] = max(dp[w], dp[w - weights[i - 1]] + values[i - 1]);
// 如果装下当前物品后价值更大,则更新dp[w]
}
}
return dp[W]; // 返回背包容量为W时的最大价值
}
int main() {
int W = 10; // 背包容量
int n = 4; // 物品数量
int weights[] = {2, 3, 4, 5}; // 物品重量
int values[] = {3, 4, 5, 6}; // 物品价值
int max_value = knapsack_01(W, n, weights, values);
printf("The maximum value in knapsack is: %d\n", max_value);
return 0;
}
3、贪心算法(Greedy Algorithm)
思想:在每一步选择中都采取在当前状态下最好或最优(即最有利 )的选择,从而希望导致结果是全局最好或最优的算法。
经典问题:活动选择问题(Activity Selection Problem)
cue: 给定一系列活动,每个活动都有一个开始时间和结束时间。如何选择尽可能多的活动,使得这些活动在时间上不重叠?
#include <stdio.h>
#include <stdlib.h>
// 活动结构体
typedef struct {
int start; // 开始时间
int finish; // 结束时间
} Activity;
// 比较函数,用于qsort
int compare(const void *a, const void *b) {
Activity *actA = (Activity *)a;
Activity *actB = (Activity *)b;
return actA->finish - actB->finish; // 按结束时间排序
}
// 活动选择函数
int activitySelection(Activity arr[], int n) {
// 首先按结束时间对活动进行排序 排序的作用就是贪心
qsort(arr, n, sizeof(Activity), compare);
int count = 1; // 至少可以选择一个活动
int last = 0; // 最后一个被选择的活动索引
for (int i = 1; i < n; i++) {
// 如果当前活动的开始时间大于或等于上一个被选择活动的结束时间
// 则可以选择当前活动
if (arr[i].start >= arr[last].finish) {
count++;
last = i;
}
}
return count;
}
int main() {
Activity arr[] = {{0, 6},{1, 2}, {3, 4}, {5, 7}, {8, 9}, {5, 9}};
int n = sizeof(arr) / sizeof(arr[0]);
int max_activities = activitySelection(arr, n);
printf("Maximum number of activities that can be selected is: %d\n", max_activities);
return 0;
}
4、回溯法(Backtracking)
思想:通过探索所有可能的候选解来找出所有的解。如果候选解被确认不是一个解(或者至少不是最后一个解),则回溯到上一步尝试其他选择。
经典问题:八皇后问题(N-Queens Problem)
cue: 在N×N的棋盘上放置N个皇后,使得任何两个皇后都不在同一行、同一列或同一对角线上。如何找到所有可能的解决方案?
#include <stdio.h>
int place[8] = {0}; // 皇后位置
int flag[8] = {1, 1, 1, 1, 1, 1, 1, 1}; // 定义列
int d1[15] = {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}; // 定义上对角线(共有15个对角线,
// 因此定义一个长度为15的数组,初值为1代表该对角线没有被皇后占领,
// 若被皇后占领则赋值为0
int d2[15] = {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}; // 定义下对角线
int count = 0; // 记录输出次数
void print() // 定义输出函数
{
int i, j;
count++; // 每调用一次输出函数number自加一次,记录摆放方法个数
printf("No.%2d\n", count);
int table[8][8] = {0}; // 设置一个8*8的棋盘
for (i = 0; i < 8; i++)
{
table[i][place[i]] = 1; // 将每一行皇后所在位置赋值为1
}
for (i = 0; i < 8; i++)
{
for (j = 0; j < 8; j++)
{
printf("%d|", table[i][j]);
}
printf("\n");
}
}
int queen(int n) // 定义递归回溯函数
{
int col;
for (col = 0; col < 8; col++)
{
if (flag[col] && d1[n - col + 7] && d2[n + col]) // 判断皇后是否冲突
{
place[n] = col; // 放置皇后
flag[col] = 0;
d1[n - col + 7] = 0;
d2[n + col] = 0; // 将该皇后所在的行、列、对角线设置为被占领
if (n < 7)
{
queen(n + 1);
} // 当行数小于7时;递归调用下一行
else
{
print();
} // 调用输出函数
flag[col] = 1; // 回溯
d1[n - col + 7] = 1;
d2[n + col] = 1;
}
}
return count;
}
int main()
{
count = queen(0); // 从第0行开始摆放皇后
printf("共有%d种方法", count); // 输出摆放皇后的方法个数
return 0;
}
5、分支限界法(Branch and Bound)
思想:类似于回溯法,但使用了剪枝技术来避免搜索一些不可能产生最优解的子空间。
经典问题:旅行商问题(Traveling Salesman Problem,TSP)的近似解
cue: 给定一系列城市和每对城市之间的距离,如何找到一条访问每个城市一次并返回起点的最短可能路线?分支限界法通过限制搜索空间来找到TSP的近似解。
#include <stdio.h>
#include <stdbool.h>
#include <limits.h>
#define CITY_COUNT 5 // 假设有5个城市
// 假设的距离矩阵,需要根据你的具体问题来设置
int distance_matrix[CITY_COUNT][CITY_COUNT] = {
{0, 10, 15, 20, 25},
{10, 0, 35, 25, 30},
{15, 35, 0, 30, 35},
{20, 25, 30, 0, 20},
{25, 30, 35, 20, 0}};
// 假设的初始和最小成本
int initial_cost = 0;
int min_cost = INT_MAX;
// 路径数组,存储当前路径
int path[CITY_COUNT + 1]; // 多一个位置用于存储起点
// 标记数组,用于跟踪哪些城市已被访问
bool visited[CITY_COUNT] = {false};
// 递归函数来搜索路径
void tsp(int current_city, int current_cost)
{
// 如果所有城市都已访问过
if (current_city == CITY_COUNT)
{
// 添加起点到终点的距离
current_cost += distance_matrix[current_city - 1][0];
// 如果找到了更短的路径,则更新
if (current_cost < min_cost)
{
min_cost = current_cost;
// 可以在这里打印或存储最短路径
for (int i = 0; i <= CITY_COUNT; i++)
{
printf("%d ", path[i]);
}
printf("(%d)\n", current_cost);
}
return;
}
// 遍历所有未访问的城市
for (int next_city = 0; next_city < CITY_COUNT; next_city++)
{
if (!visited[next_city])
{
// 将下一个城市标记为已访问,并添加到路径中
visited[next_city] = true;
path[current_city] = next_city;
// 计算当前路径的成本
int new_cost = current_cost + distance_matrix[path[current_city - 1]][next_city];
// 递归地搜索下一个城市
tsp(current_city + 1, new_cost);
// 回溯
visited[next_city] = false;
}
}
}
int main()
{
// 初始化路径的起点
path[0] = 0;
visited[0] = true;
// 开始搜索
tsp(1, initial_cost);
printf("Minimum cost: %d\n", min_cost);
return 0;
}