1. 贪心法（Greedy Algorithm）

1.1 贪心法的基本思想

贪心法总是做出在当前看来是最好的选择。也就是说，贪心法并不从整体最优上加以考虑，它所做出的选择只是在某种意义上的局部最优解。

贪心法的特点：

  • 贪心策略一旦做出，不可回溯
  • 贪心法求解的问题需要满足贪心选择性质和最优子结构性质
  • 贪心法通常自顶向下进行求解

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

1.2 实例：部分背包问题

问题描述：给定 $n$ 种物品和一个容量为 $W$ 的背包，物品 $i$ 的重量为 $w_i$，价值为 $v_i$。与0-1背包问题不同的是，在部分背包问题中，可以选择物品的一部分装入背包。

贪心策略：

按照单位重量价值（$v_i/w_i$）从大到小的顺序选取物品，直到背包装满。

C++ 代码实现：

#include <stdio.h>

#define N 5 // 物品数量
#define W 10 // 背包容量

int v_temp[N + 1], w_temp[N + 1]; // 物品价值数组 和 物品重量数组的临时数组
double vw_temp[N + 1]; // 物品单位重量价值数组的临时数组

double answer[N + 1]; // 解方案数组

// 归并排序
void merge_sort(int v[], int w[], double vw[], int l, int r) {
    if (l >= r) return;

    int mid = l + r >> 1;
    merge_sort(v, w, vw, l, mid), merge_sort(v, w, vw, mid + 1, r);

    int i = l, j = mid + 1, k = 1;
    while (i <= mid && j <= r) {
        if (vw[i] >= vw[j]) { // 按照 物品单位重量价值数组 从大到小的顺序排序
            vw_temp[k] = vw[i];
            v_temp[k] = v[i];
            w_temp[k] = w[i];

            k++, i++;
        } else {
            vw_temp[k] = vw[j];
            v_temp[k] = v[j];
            w_temp[k] = w[j];

            k++, j++;
        }
    }

    while (i <= mid) {
        vw_temp[k] = vw[i];
        v_temp[k] = v[i];
        w_temp[k] = w[i];

        k++, i++;
    }

    while (j <= r) {
        vw_temp[k] = vw[j];
        v_temp[k] = v[j];
        w_temp[k] = w[j];
        k++, j++;
    }

    for (i = l, j = 1; i <= r; i++, j++) {
        vw[i] = vw_temp[j];
        v[i] = v_temp[j];
        w[i] = w_temp[j];
    }
}

// 显示物品价值、重量、单位重量价值数组
void show(int v[], int w[], double vw[]) {
    int i;

    printf("物品价值数组：");
    for (i = 1; i <= N; i++) printf("%d ", v[i]);
    printf("\n");

    printf("物品重量数组：");
    for (i = 1; i <= N; i++) printf("%d ", w[i]);
    printf("\n");

    printf("物品单位重量价值数组：");
    for (i = 1; i <= N; i++) printf("%.1lf ", vw[i]);
    printf("\n");
}

// 求解部分背包问题最优解
double Max_Value(int v[], int w[], double vw[]) {
    double result = 0.0;

    int i;
    int W_temp = W;
    for (i = 1; i <= N; i++) {
        if (W_temp >= w[i]) { // 当前背包容量 大于等于 物品重量 就直接全部装入到背包中
            answer[i] = 1.0;

            result = result + v[i];

            W_temp = W_temp - w[i];
        } else { // 当前背包容量 小于 物品重量 就应该将该物品的一部分装入到背包中
            break;
        }
    }

    if (W_temp > 0 && i <= N) { // 当前背包还有剩余容量 并且 还有可选的物品
        answer[i] = (double) W_temp / w[i];

        result = result + W_temp * vw[i];
    }

    return result;
}

int main() {
    int v[] = {0, 6, 3, 5, 4, 6}; // 物品价值数组
    int w[] = {0, 2, 2, 6, 5, 4}; // 物品重量数组

    double vw[N + 1]; // 物品单位重量价值数组

    int i;
    // 初始化 物品单位重量价值数组
    for (i = 1; i <= N; i++) vw[i] = (double) v[i] / w[i];

    printf("排序前：\n");
    show(v, w, vw);

    merge_sort(v, w, vw, 1, N);

    printf("排序后：\n");
    show(v, w, vw);

    double result = Max_Value(v, w, vw);
    printf("\nresult = %.2lf\n", result);
    printf("\n");

    printf("解方案结果：");
    for (i = 1; i <= N; i++) printf("%.1lf ", answer[i]);

    return 0;
}

1.3 贪心法的其他应用

问题 贪心策略
活动选择问题 每次选择结束时间最早的活动
哈夫曼编码 每次选择频率最小的两个节点合并
最小生成树（Prim/Kruskal） 每次选择权重最小的边
单源最短路径（Dijkstra） 每次选择距离源点最近的顶点

2. 回溯法（Backtracking）

2.1 回溯法的算法框架

回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择。

回溯法的特点：

  • 采用深度优先搜索策略
  • 在搜索过程中用剪枝函数避免无效搜索
  • 适用于求解组合数较大的问题

回溯法的基本步骤：

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

2.2 实例：N皇后问题

问题描述：给定一个 $N \times N$ 的棋盘，要在棋盘上摆放 $N$ 个皇后，并且满足 $N$ 个皇后中任意两个皇后都不处于同一行、同一列、同一斜线上（正斜线、反斜线）。

2.2.1 非递归方式

#include <math.h>
#include <stdio.h>

#define N 10

int q[N + 1]; // 存储皇后的列号

int check(int j) { // 检查第 j 个皇后的位置是否合法
    int i;
    for (i = 1; i < j; i++) {
        if (q[i] == q[j] || abs(i - j) == abs(q[i] - q[j])) { // 判断是否在同一列或同一斜线
            return 0;
        }
    }

    return 1;
}

void queen() { // 求解 N 皇后 方案
    int i;
    for (i = 1; i <= N; i++) {
        q[i] = 0;
    }

    int answer = 0; // 方案数

    int j = 1; // 表示正在摆放第 j 个皇后
    while (j >= 1) {
        q[j] = q[j] + 1; // 让第 j 个皇后向后一列摆放

        while (q[j] <= N && !check(j)) { // 判断第 j 个皇后的位置是否合法
            q[j] = q[j] + 1; // 不合法就往后一个位置摆放
        }

        if (q[j] <= N) { // 表示第 j 个皇后的找到一个合法的摆放位置
            if (j == N) { // 找到了 N 皇后的一组解
                answer = answer + 1;
                printf("方案%d：", answer);

                for (i = 1; i <= N; i++) {
                    printf("%d ", q[i]);
                }
                printf("\n");
            } else {
                j = j + 1; // 继续摆放下一个皇后
            }
        } else { // 表示第 j 个皇后找不到一个合法的摆放位置
            q[j] = 0; // 还原第 j 个皇后的位置
            j = j - 1; // 回溯
        }
    }
}

int main() {
    queen();
    return 0;
}

2.2.2 递归方式

#include <math.h>
#include <stdio.h>

#define N 10

int answer = 0;
int q[N + 1]; // 存储皇后的列号

int check(int j) { // 检查第 j 个皇后的位置是否合法
    int i;
    for (i = 1; i < j; i++) {
        if (q[i] == q[j] || abs(i - j) == abs(q[i] - q[j])) { // 判断是否在同一列或同一斜线
            return 0;
        }
    }

    return 1;
}

void queen(int j) {
    int i;
    for (i = 1; i <= N; i++) {
        q[j] = i;

        if (check(j)) { // 当摆放的皇后位置为合法时
            if (j == N) { // 找到了 N 皇后的一组解
                answer = answer + 1;
                printf("方案%d：", answer);

                for (i = 1; i <= N; i++) {
                    printf("%d ", q[i]);
                }
                printf("\n");
            } else {
                queen(j + 1); // 递归摆放下一个皇后的位置
            }
        }
    }
}

int main() {
    queen(1);
    return 0;
}

3. 贪心法与回溯法的比较

特性 贪心法 回溯法
决策方式 每步做出局部最优选择，不可回溯 试探性选择，可回溯
搜索策略 自顶向下，一次决策 深度优先搜索
解的性质 不一定得到全局最优解 可以得到所有可行解或最优解
效率 效率高，时间复杂度低 效率较低，可能需要遍历大量节点
适用场景 具有贪心选择性质的问题 组合优化、约束满足问题
典型问题 部分背包、最小生成树、最短路径 N皇后、子集和、图着色、旅行商

4. 四种算法设计策略总结

算法策略 核心思想 典型问题 时间复杂度特点
分治法 分解 → 解决 → 合并 归并排序、快速排序、最大子段和 通常 $O(n \log n)$
动态规划 填表法，保存子问题解 0-1背包、最长公共子序列 通常多项式时间
贪心法 局部最优选择 部分背包、最小生成树 通常线性或对数时间
回溯法 深度优先搜索 + 剪枝 N皇后、子集和 指数级，但可剪枝优化