算法导论笔记

算法概述

算法的定义

算法是由若⼲条指令组成的有穷序列

算法的性质

输入、输出、确定性、有限性

程序与算法的区别

程序是算法用某种程序设计语言的具体实现
程序可以不满足算法的有限性

问题求解

图 0

算法复杂度

复杂性的计量

C = F(N,I,A) \implies T = T(N,I), S = S(N,I)

其中， $N$ 为问题规模， $I$ 为问题的输入， $A$ 为算法， $F$ 为复杂性函数， $T$ 为时间复杂度， $S$ 为空间复杂度， $C$ 为复杂性

时间复杂度

T = T(N,I) = \sum\limits_{i=1}^{k} t_i e_i(N,I)

其中， $t_i$ 为第 $i$ 条指令的执行时间（元运算时间）， $e_i(N,I)$ 为第 $i$ 条指令的执行次数（元运算次数）， $k$ 为算法的指令数（元运算种类）

不可能精确计算出 $T(N,I)$ ，只能估计

最坏情况时间复杂度： $T_{\max}(N) = \max\limits_{I \in D_N} T(N,I) = \max\limits_{I \in D_N} \sum\limits_{i=1}^{k} t_i e_i(N,I) = \sum\limits_{i=1}^{k} t_i e_i(N,I^\ast) = T(N, I^\ast)$ ，其中 $I^\ast$ 为使得 $T(N,I)$ 最大的输入
最好情况时间复杂度： $T_{\min}(N) = \min\limits_{I \in D_N} T(N,I) = \sum\limits_{i=1}^{k} t_i e_i(N,\tilde{I}) = T(N, \tilde{I})$ ，其中 $\tilde{I}$ 为使得 $T(N,I)$ 最小的输入
平均时间复杂度： $T_{\text{avg}}(N) = \sum\limits_{I \in D_N} P(I) T(N,I) = \sum\limits_{I \in D_N} P(I) \sum\limits_{i=1}^{k} t_i e_i(N,I)$ ，其中 $P(I)$ 为输入 $I$ 出现的概率

可操作性最好且最有实际价值的是最坏情况下的复杂度

复杂性的渐进性态

渐进性态

设 $T(N)$ 为算法 $A$ 的时间复杂度，则它是 $N$ 的单增函数。如果存在一个函数 $\tilde{T}(N)$ ，使得对于 $N \rightarrow \infty$ ，有 $\frac{T(N)-\tilde{T}(N)}{T(N)} \rightarrow 0$ ，则称 $\tilde{T}(N)$ 是 $T(N)$ 当 $N \rightarrow \infty$ 时的渐进性态（渐进复杂性）

渐进性态的阶

设 $f(N)$ 和 $g(N)$ 是定义在正整数集合上的正函数

大 $O$ 表示法（上限）

如果存在正常数 $C$ 和 $N_0$ ，使得对于一切 $N>N_0$ ，有 $f(N) \leq Cg(N)$ ，则称 $f(N)$ 在 $N \rightarrow \infty$ 时有上界，且 $g(N)$ 是 $f(N)$ 的一个上界，记作 $f(N) = O(g(N))$

上界的阶越低，则评估越精确，结果就越有价值。

$O(f) + O(g) = O(\max(f,g))$
$O(f) + O(g) = O(f+g)$
$O(f) \cdot O(g) = O(f \cdot g)$
如果 $g(N) = O(f(N))$ ，则 $O(f) + O(g) = O(f)$
$f = O(f)$
$O(Cf(N)) = O(f(N))$

图 1

大 $\Omega$ 表示法（下限）

如果存在正常数 $C$ 和 $N_0$ ，使得对于一切 $N>N_0$ ，有 $f(N) \geq Cg(N)$ ，则称 $f(N)$ 在 $N \rightarrow \infty$ 时有下界，且 $g(N)$ 是 $f(N)$ 的一个下界，记作 $f(N) = \Omega(g(N))$

下界的阶越高，则评估越精确，结果就越有价值。

大 $\Theta$ 表示法

$f(N) = \Theta(g(N))$ ，当且仅当 $f(N) = O(g(N))$ 且 $f(N) = \Omega(g(N))$ ，称 $f(N)$ 与 $g(N)$ 同阶

NP完全性理论

P类问题

多项式时间内可解决的问题

NP类问题

多项式时间内可验证的问题，NP问题不要求给出一个算法来求解问题本身,而只要求给出一个确定性算法在多项式时间内验证它的解

递归与分治策略

递归的概念

递归函数：用函数自身定义的函数，两要素：边界条件与递归方程
递归算法：直接或间接调用自身的算法
双递归函数：一个函数及它的一个变量是由函数自身定义（不能转换成循环）

排列问题

设 $R = \{r_1, r_2, \dots, r_n\}$ 是要进行排列的 $n$ 个元素， $R = R - \{r\}$ 。集合 $X$ 中元素的全排列记为 $Perm(X)$ 。 $(r)Perm(X)$ 表示在全排列 $Perm(X)$ 的每个排列前加上前缀 $r$ 得到的排列。 $R$ 的全排列可归纳定义如下：

当 $n = 1$ 时， $Perm(R) = (r)$ ，其中 $r$ 是集合 $R$ 中唯一的元素；
当 $n > 1$ 时， $Perm(R) = \{ r_1 Perm(R_1), r_2 Perm(R_2), \dots, r_n Perm(R_n) \}$ 。

依此递归定义，可设计产生 $Perm(R)$ 的递归算法如下：

template <class T>
void Perm(T list[], int k, int m) { // 产生list[ ]数组中从k到m元素的全排列.
  if (k == m) {    // 只剩下一个元素
    for (int i = 0; i <= m; i++)
      cout << list[i];
    cout << endl;
  } else // 还有多个元素，递归产生排列
    for (int i = k; i <= m; i++) {
      swap(list[k], list[i]); // 固定第一个元素
      Perm(list, k + 1, m);
      swap(list[k], list[i]); // !还原，不然会有重复排列
    }
}

整数划分

将正整数 $n$ 表示成一系列正整数之和， $n = n_1 + n_2 + \dots + n_k$ （ $n \geq n_1 \geq \dots \geq n_k \geq 1, \ k \geq 1$ ）。正整数 $n$ 的这种表示称为正整数 $n$ 的划分。正整数 $n$ 的不同的划分个数称为正整数 $n$ 的划分数，记为 $p(n)$ 。

q(n,m) = \begin{cases} 1 & n=1,m=1\\ q(n,n) & n<m\\ 1+q(n,n-1) & n=m\\ q(n,m-1)+q(n-m,m) & n>m>1 \end{cases}

对于数据n，最大加数n1不大于m的划分个数记作q(n, m)。

int q(int n, int m) {
  // 如果n或m小于1，没有有效的划分
  if ((n < 1) || (m < 1))
    return 0;

  // 如果n或m等于1，只有一种划分方式
  if ((n == 1) || (m == 1))
    return 1;

  // 如果n小于m，将m调整为n，避免重复计算
  if (n < m)
    return q(n, n);

  // 如果n等于m，增加一种包含m本身的划分
  if (n == m)
    return q(n, m - 1) + 1;

  // 递归计算不包含m的划分数量加上包含m的划分数量
  return q(n, m - 1) + q(n - m, m);

  // 示例说明：
  // q(6, 4) = q(6, 3) + q(2, 4)
  // q(n - m, m) 固定了6 = 4 + x中的4，只对x进行讨论
}

递归的优缺点

优点：
- 算法简明；
- 正确性易证明，是分析、设计的有力工具。
缺点：
- 执行效率不高；
- 堆栈空间耗费

分治法

分治法所能解决的问题特征

该问题可以分解为若干个规模较小的相同问题；
该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题；
该问题的规模缩小到一定的程度就可以容易地解决；
利用该问题分解出的子问题的解可以合并为该问题的解。

分治法基本思想

将规模为 $n$ 的问题分解为 $k$ 个规模较小的子问题，使这些子问题相互独立且与原问题相同，递归地解这些子问题，然后各个子问题的解合并得到原问题的解。

分治法基本步骤

Divide-and-Conquer(P):
  if |P| ≤ n₀:
    return Adhoc(P)
  divide P into P₁, P₂, ..., Pₖ
  for i from 1 to k:
    yᵢ = Divide-and-Conquer(Pᵢ)
  return Merge(y₁, y₂, ..., yₖ)

分治法求解过程

分解：把原问题分解为若干个规模较小、相互独立，与原问题相同的子问题；
求解：若子问题规模较小且容易被解决则直接解，否则再继续分解为更小的子问题，直到容易解决；
合并：将已求解的各个子问题的解，逐步合并为原问题的解。

分治法的时间复杂性

设 $T(n)$ 为规模为 $n$ 的问题的解所需的时间，则有

T(n) \leq \begin{cases} O(1) & n = n_0\\ kT(\frac{n}{m}) + f(n) & n > n_0 \end{cases}

其中， $k$ 为分解出的子问题个数， $m$ 为分解问题的规模， $f(n)$ 为合并子问题解的时间

设 $n=m^a$ ，则有 $a=\log_m n$ ，则有

k^a=k^{\log_m n}=n^{\log_m k}

T(n) = n^{\log_m k}T(1) + \sum\limits_{i=0}^{\log_m n-1} k^i f(\frac{n}{m^i})

二分法

template <class T>
int BinarySearch(T a[], const T &x, int n) {
  int left = 0, right = n - 1; // 初始化左右边界
  while (left <= right) { // 当左边界小于等于右边界时继续搜索
    int middle = (left + right) / 2; // 计算中间位置
    if (x == a[middle]) // 如果找到目标值，返回其位置
      return middle;
    if (x > a[middle]) // 如果目标值大于中间值，调整左边界
      left = middle + 1;
    else // 如果目标值小于中间值，调整右边界
      right = middle - 1;
  }
  return -1; // 如果未找到目标值，返回-1
}

递推式： $T(n)=\begin{cases}O(1) & n=1\\T(\frac{n}{2})+O(1) & n>1\end{cases}$
时间复杂度： $O(\log n)$

找金块

老板有一袋金块（共 $n$ 块， $n$ 是2的幂（ $n≥2$ ）），最优秀的雇员得到其中最重的一块，最差的雇员得到其中最轻的一块。假设有一台比较重量的仪器，希望用最少的比较次数找出最重和最轻的金块

auto findMaxandMin(vector<int> &gold) {
  // 如果数组只有两个元素，直接返回最大值和最小值
  if (gold.size() == 2) {
    return gold[0] > gold[1] ? make_pair(gold[0], gold[1])
                             : make_pair(gold[1], gold[0]);
  }
  // 将数组分成左右两部分
  vector<int> left(gold.begin(), gold.begin() + gold.size() / 2);
  vector<int> right(gold.begin() + gold.size() / 2, gold.end());
  // 递归求解左右两部分的最大值和最小值
  pair<int, int> leftMaxNMin = findMaxandMin(left);
  pair<int, int> rightMaxNMin = findMaxandMin(right);
  // 返回左右两部分的最大值和最小值
  return make_pair(max(leftMaxNMin.first, rightMaxNMin.first),
                   min(leftMaxNMin.second, rightMaxNMin.second));
}

棋盘覆盖

在一个 $2^k \times 2^k$ 的棋盘中，有一个方格与其他方格不同，要求用L型骨牌覆盖其余方格
用分治法解决，将棋盘分为四个 $2^{k-1} \times 2^{k-1}$ 的子棋盘，分别覆盖，特殊方格必位于其中一个子棋盘中，其余三个子棋盘的特殊方格用L型骨牌覆盖

/**
  * @brief 棋盘覆盖
  * @param tr 棋盘左上角行号
  * @param tc 棋盘左上角列号
  * @param dr 特殊方格行号
  * @param dc 特殊方格列号
  * @param size 棋盘大小
  */
void ChessBoard(int tr, int tc, int dr, int dc, int size) {
  if (size == 1) return; // 基本情况：棋盘大小为1时，直接返回
  int t = tile++, s = size / 2; // t表示当前L型骨牌编号，s表示子棋盘的大小

  // 覆盖左上角子棋盘
  if (dr < tr + s && dc < tc + s)
    ChessBoard(tr, tc, dr, dc, s); // 特殊方格在左上角子棋盘
  else {
    board[tr + s - 1][tc + s - 1] = t; // 用L型骨牌覆盖右下角
    ChessBoard(tr, tc, tr + s - 1, tc + s - 1, s); // 递归处理左上角子棋盘
  }

  // 覆盖右上角子棋盘
  if (dr < tr + s && dc >= tc + s)
    ChessBoard(tr, tc + s, dr, dc, s); // 特殊方格在右上角子棋盘
  else {
    board[tr + s - 1][tc + s] = t; // 用L型骨牌覆盖左下角
    ChessBoard(tr, tc + s, tr + s - 1, tc + s, s); // 递归处理右上角子棋盘
  }

  // 覆盖左下角子棋盘
  if (dr >= tr + s && dc < tc + s)
    ChessBoard(tr + s, tc, dr, dc, s); // 特殊方格在左下角子棋盘
  else {
    board[tr + s][tc + s - 1] = t; // 用L型骨牌覆盖右上角
    ChessBoard(tr + s, tc, tr + s, tc + s - 1, s); // 递归处理左下角子棋盘
  }

  // 覆盖右下角子棋盘
  if (dr >= tr + s && dc >= tc + s)
    ChessBoard(tr + s, tc + s, dr, dc, s); // 特殊方格在右下角子棋盘
  else {
    board[tr + s][tc + s] = t; // 用L型骨牌覆盖左上角
    ChessBoard(tr + s, tc + s, tr + s, tc + s, s); // 递归处理右下角子棋盘
  }
}

大整数的乘法

将 $n$ 位二进制整数 $X$ 和 $Y$ 都分为两段，每段的长为 $\frac{n}{2}$ 。

\begin{align*} X &= A \times 2^{\frac{n}{2}} + B \\ Y &= C \times 2^{\frac{n}{2}} + D \\ XY &= AC \times 2^n + (AD + BC) \times 2^{\frac{n}{2}} + BD \end{align*}

时间复杂度为：

T(n) = \begin{cases} O(1) & n=1\\ 4T(\frac{n}{2}) + O(n)& n>1 \end{cases} \implies T(n) = O(n^2)

改进：

XY = AC\times 2^n + ((A-B)(D-C)+AC+BD)\times 2^{\frac{n}{2}} + BD

时间复杂度：

T(n) = \begin{cases} O(1) & n=1\\ 3T(\frac{n}{2}) + O(n) & n>1 \end{cases} \implies T(n) = O(n^{\log 3}) = O(n^{1.59})

auto Karatsuba(const string &X, const string &Y) {
  if (X.size() == 1) {
    return to_string(stoi(X) * stoi(Y));
  }
  string A = X.substr(0, X.size() / 2);
  string B = X.substr(X.size() / 2);
  string C = Y.substr(0, Y.size() / 2);
  string D = Y.substr(Y.size() / 2);
  string AC = Karatsuba(A, C);
  string BD = Karatsuba(B, D);
  string AD_BC = to_string((stoi(A) + stoi(B)) * (stoi(C) + stoi(D)) - stoi(AC) - stoi(BD));
  return to_string(stoi(AC) * pow(10, X.size()) + stoi(AD_BC) * pow(10, X.size() / 2) + stoi(BD));
}

Strassen矩阵乘法

将两个 $n \times n$ 的矩阵分为四个 $\frac{n}{2} \times \frac{n}{2}$ 的子矩阵, 可将方程 $C = A \times B$ 分解为

\begin{bmatrix} C_{11} & C_{12} \\ C_{21} & C_{22} \end{bmatrix}= \begin{bmatrix} A_{11} & A_{12} \\ A_{21} & A_{22} \end{bmatrix} \times \begin{bmatrix} B_{11} & B_{12} \\ B_{21} & B_{22} \end{bmatrix}

时间复杂度：

T(n) = \begin{cases} O(1) & n=2\\ 8T(\frac{n}{2}) + O(n^2) & n>2 \end{cases} \implies T(n) = O(n^3)

改进：将矩阵分解为七个 $\frac{n}{2} \times \frac{n}{2}$ 的子矩阵，可将时间复杂度降为 $O(n^{\log 7})$

\begin{aligned} M_1 = A_{11}(B_{12}-B_{22}) \\ M_2 = (A_{11}+A_{12})B_{22} \\ M_3 = (A_{21}+A_{22})B_{11} \\ M_4 = A_{22}(B_{21}-B_{11}) \\ M_5 = (A_{11}+A_{22})(B_{11}+B_{22}) \\ M_6 = (A_{12}-A_{22})(B_{21}+B_{22}) \\ M_7 = (A_{11}-A_{21})(B_{11}+B_{12}) \end{aligned}

可得：

\begin{aligned} C_{11} &= M_5+M_4-M_2+M_6 \\ C_{12} &= M_1+M_2 \\ C_{21} &= M_3+M_4 \\ C_{22} &= M_5+M_1-M_3-M_7 \end{aligned}

时间复杂度：

T(n) = \begin{cases} O(1) & n=2\\ 7T(\frac{n}{2}) + O(n^2) & n>2 \end{cases} \implies T(n) = O(n^{\log 7}) = O(n^{2.81})

合并排序

将一个数组分为两个规模相等的子数组，分别排序，然后将两个有序子数组合并为一个有序数组

void mergeSort(std::vector<int>& arr) {
    if (arr.size() <= 1)
        return;

    size_t mid = arr.size() / 2;
    std::vector<int> left(arr.begin(), arr.begin() + mid);
    std::vector<int> right(arr.begin() + mid, arr.end());

    mergeSort(left);
    mergeSort(right);

    std::merge(left.begin(), left.end(), right.begin(), right.end(), arr.begin());
}
// 一种merge实现
template <typename T>
void my_merge(const std::vector<T>& left, const std::vector<T>& right, std::vector<T>& result) {
    size_t i = 0, j = 0;
    result.reserve(left.size() + right.size());

    while(i < left.size() && j < right.size()) {
        if(left[i] <= right[j]) {
            result.push_back(left[i++]);
        }
        else {
            result.push_back(right[j++]);
        }
    }

    while(i < left.size()) {
        result.push_back(left[i++]);
    }

    while(j < right.size()) {
        result.push_back(right[j++]);
    }
}

时间复杂度：

T(n) = \begin{cases} O(1) & n=1\\ 2T(\frac{n}{2}) + O(n) & n>1 \end{cases} \implies T(n) = O(n\log n)

改进：消除算法中的递归：自然归并排序

template <typename T>
void MergeSort(T a[], int n) {
  T *b = new T[n]; // 动态分配辅助数组
  int s = 1; // 初始子数组大小为1
  while (s < n) {
    MergePass(a, b, s, n); // 将数组a中的子数组合并到b中
    s += s; // 子数组大小加倍
    MergePass(b, a, s, n); // 将数组b中的子数组合并到a中
    s += s; // 子数组大小加倍
  }
  delete[] b; // 释放辅助数组
}

template <typename T>
void MergePass(T a[], T b[], int s, int n) {
  int i = 0;
  while (i <= n - 2 * s) {
    Merge(a, b, i, i + s - 1, i + 2 * s - 1); // 合并相邻的两个子数组
    i = i + 2 * s; // 移动到下一个待合并的子数组
  }
  if (i + s < n) Merge(a, b, i, i + s - 1, n - 1); // 合并最后两个子数组
  else
    for (int j = i; j < n; j++) b[j] = a[j]; // 将剩余的元素复制到b中
}

template <typename T>
void Merge(T a[], T b[], int l, int m, int n) {
  int i = l, j = m + 1, k = l;
  while (i <= m && j <= n) {
    if (a[i] <= a[j])
      b[k++] = a[i++]; // 将较小的元素复制到b中
    else
      b[k++] = a[j++]; // 将较小的元素复制到b中
  }
  while (i <= m) b[k++] = a[i++]; // 将剩余的左半部分元素复制到b中
  while (j <= n) b[k++] = a[j++]; // 将剩余的右半部分元素复制到b中
}

快速排序

选取一个基准元素，将小于基准元素的元素放在基准元素的左边，大于基准元素的元素放在基准元素的右边，然后递归地对左右两部分进行排序

template <typename T>
int partition(T a[], int p, int r) {
  int i = p, j = r + 1;
  T x = a[p]; // 基准值 x

  while (true) {
    while (a[++i] < x && i < r)
      ; // 左指针 i 向右扫描
    while (a[--j] > x)
      ; // 右指针 j 向左扫描

    if (i >= j)
      break; // 当 i >= j 时退出循环

    swap(a[i], a[j]); // 交换 a[i] 和 a[j]
  }

  a[p] = a[j]; // 基准值放到最终位置
  a[j] = x;    // j 为基准值的位置
  return j;    // 返回基准值最终位置
}

template <typename T>
void quickSort(T a[], int l, int r) {
  if (l < r) {
    int pivot = partition(a, l, r);
    quickSort(a, l, pivot - 1);
    quickSort(a, pivot + 1, r);
  }
}

什么时候以i > j退出循环？什么时候以i == j退出循环？{.quiz .fill}

i > j 正常情况
i == j 当 a[i] 和 a[j] 都等于基准值时（数组中有且只有奇数个等于基准值的元素）或数组递减

时间复杂度：

T(n) = \begin{cases} O(1) & n=1\\ T(i-1)+T(n-i)+O(n) & n>1 \end{cases} \implies T(n) = O(n\log n)

最坏情况下时间复杂度为

T(n) = \begin{cases} O(1) & n=1\\ T(n-1)+O(n) & n>1 \end{cases} \implies T(n) = O(n^2)

改进：随机化快速排序

template <typename T>
int RandomizedPartition(T a[], int l, int r) {
  int i = rand() % (r - l + 1) + l;
  swap(a[i], a[l]);
  return partition(a, l, r);
}

template <typename T>
void RandomizedQuickSort(T a[], int l, int r) {
  if (l < r) {
    int pivot = RandomizedPartition(a, l, r);
    RandomizedQuickSort(a, l, pivot - 1);
    RandomizedQuickSort(a, pivot + 1, r);
  }
}

线性时间选择

给定线性序列 $X$ 和整数 $k$ ，求 $X$ 中第 $k$ 小的元素

思路：
随机选取一个元素作为基准元素，将小于基准元素的元素放在基准元素的左边，大于基准元素的元素放在基准元素的右边，若基准元素的位置为 $k$ ，则返回基准元素，否则递归地在左边或右边进行查找

template <typename T>
T RandomizedSelect(T a[], int low, int high, int k) {
  if (low == high) return a[low];
  int pivot = RandomizedPartition(a, low, high);
  int i = pivot - low + 1; // 前半部分元素个数
  if (k <= i) return RandomizedSelect(a, low, pivot, k);
  else return RandomizedSelect(a, pivot + 1, high, k - i);
}

时间复杂度：

T(n) = \begin{cases} O(1) & n=1\\ T(\frac{n}{2})+O(n) & n>1 \end{cases} \implies T(n) = O(n)

优化
选取基准点时，不是随机选取，而是选取中位数的中位数

将序列分为 $\lceil\frac{n}{5}\rceil$ 组，找出每组的中位数
递归地找出这些中位数的中位数，以这个中位数的中位数作为基准点

template <typename T>
T Select(T a[], int low, int high, int k) {
  if (high - low < 75) {
    sort(a + low, a + high + 1);
    return a[low + k - 1];
  }
  // 计算五元组的数量
  int numMedians = (high - low + 1 + 4) / 5;
  for (int i = 0; i < numMedians; i++) {
    // 获取五元组的起始和结束位置
    int subLow = low + i * 5;
    int subHigh = min(subLow + 4, high);
    // 对五元组进行排序
    sort(a + subLow, a + subHigh + 1);
    // 将五元组的中位数放到数组前部
    swap(a[low + i], a[subLow + (subHigh - subLow) / 2]);
  }
  // 递归调用 Select 获取中位数的中位数
  T pivot = Select(a, low, low + numMedians - 1, (numMedians + 1) / 2);
  // 按照主元 pivot 进行划分
  int idx = partition(a, low, high, pivot);
  int i = idx - low + 1;
  if (k == i)
    return a[idx];
  else if (k < i)
    return Select(a, low, idx - 1, k);
  else
    return Select(a, idx + 1, high, k - i);
}

最接近点对问题

一维最接近点对

给定一组一维坐标，求最接近的两个点

排序 $O(n\log n)$
分治
合并

template <typename T> T ClosestPair(vector<T> &S) {
  auto len = S.size();
  if (len < 2)
    return numeric_limits<T>::max(); // 返回一个最大值表示无效情况
  auto m = len / 2;
  auto S1 = vector<T>(S.begin(), S.begin() + m);
  auto S2 = vector<T>(S.begin() + m, S.end());
  auto d1 = ClosestPair(S1);
  auto d2 = ClosestPair(S2);
  auto d3 = abs(S2.front() - S1.back());
  return min({d1, d2, d3});
}

时间复杂度：

T(n) = \begin{cases} O(1) & n<4\\ 2T(\frac{n}{2})+O(n\log n) & n>=4 \end{cases} \implies T(n) = O(n\log n)

二维最接近点对

给定平面上 $n$ 个点，求最接近的两个点

选取一垂直线（x坐标中位数）将平面分为两部分，分别求出两部分的最接近点对，
然后求出跨越垂直线的最接近点对，易证矩形中最多只有6个点

图 2

class Point {
public:
  double x, y;
  Point(double x, double y) : x(x), y(y) {}

  // 计算两个点的欧几里得距离
  auto operator-(const Point &p) const {
    return sqrt(pow(x - p.x, 2) + pow(y - p.y, 2));
  }
};

double ClosestPair2D(vector<Point> &S) {
  auto len = S.size();
  if (len < 2)
    return numeric_limits<double>::max(); // 无效情况，返回最大值

  if (len == 2)
    return S[0] - S[1];

  if (len == 3)
    return min({S[0] - S[1], S[1] - S[2], S[0] - S[2]});

  // 按x坐标排序
  sort(S.begin(), S.end(),
       [](const Point &a, const Point &b) { return a.x < b.x; });

  auto m = len / 2;
  auto S1 = vector<Point>(S.begin(), S.begin() + m); // 左半部分
  auto S2 = vector<Point>(S.begin() + m, S.end());   // 右半部分

  // 递归计算左右两部分的最小距离
  auto d1 = ClosestPair2D(S1);
  auto d2 = ClosestPair2D(S2);

  double d = min(d1, d2); // 获取左右两部分的最小距离

  // 查找分界线附近的最接近点对
  vector<Point> strip; // 存放x坐标在d范围内的点
  for (const auto &p : S) {
    if (abs(p.x - S[m].x) < d) {
      strip.push_back(p);
    }
  }

  // 按y坐标排序
  sort(strip.begin(), strip.end(),
       [](const Point &a, const Point &b) { return a.y < b.y; });

  // 查找strip中距离小于d的点对
  for (size_t i = 0; i < strip.size(); ++i) {
    for (size_t j = i + 1; j < strip.size() && (strip[j].y - strip[i].y) < d;
         ++j) {
      d = min(d, strip[i] - strip[j]);
    }
  }

  return d; // 返回最小距离
}

动态规划

动态规划的基本思想

与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。
与分治法不同的是，适合用动态规划求解的问题，经分解得到的子问题往往不是相互独立的。

动态规划的实质

动态规划的实质是分治思想和解决冗余。

一种将问题实例分解为更小的、相似的子问题。
存储子问题的解而避免计算重复的子问题。

动态规划的特点

动态规划法用于最优化问题，这类问题会有多种可能的解，而动态规划找出其中最优值的解。
对于重复出现的子问题，只在第一次遇到时加以求解，并把答案保存起来，以后再遇到时不必重新求解。

动态规划的基本步骤

分析最优解的性质，并刻划其结构特征；
递归地定义最优值；
以自底向上的方式计算出最优值；
根据递归计算最优值时得到的信息，从子问题的最优解逐步构造出整个问题的最优解

动态规划基本要素

最优子结构性质

当问题的最优解包含了其子问题的最优解时，称该问题具有最优子结构性质。

A_1,A_2,\cdots,A_n \implies \begin{cases} A_1,A_2,\cdots,A_{k}\\ A_{k+1},A_{k+2},\cdots,A_n \end{cases}

假设由最优解导出的其子问题的解不是最优的;
构造出比原问题最优解更好的解；

重叠子问题性质

每一个子问题只解一次，而后将其解保存在一个表格中，当再次需要解此子问题时，只是简单地用常数时间查看一下结果。

矩阵连乘问题

给定 $n$ 个矩阵 $A_1,A_2,\cdots,A_n$ ，其中 $A_i$ 与 $A_{i+1}$ 是可乘的，求矩阵连乘的最优计算次序

定义 $A[i:j]$ 为 $A_i,A_{i+1},\cdots,A_j$ 的连乘积， $m[i][j]$ 为计算 $A[i:j]$ 所需的标量乘法次数

分析最优解结构

设 $A[1:n]$ 的最优计算次序为 $A[1:k]A[k+1:n]$ ，则有子矩阵链 $A[1:k]$ 和 $A[k+1:n]$ 的计算次序也应该是最优的。

反证法：
设 $A[1:n]=A[1:k]A[k+1:n]$ 的计算次序是最优的，若存在一个计算次序 $A'[1:k]$ 其需要的标量乘法次数少于 $A[1:k]$ ，则 $A'[1:k]A[k+1:n]$ 的计算次序也应该是最优的，与假设矛盾。
可以证明矩阵连乘问题具有最优子结构性质。

建立递归关系

m[i][j]=\begin{cases} 0 & i=j\\ \min\limits_{i\leq k<j}\{m[i][k]+m[k+1][j]+p_{i-1}p_kp_j\} & i<j \end{cases}

为什么是 $p_{i-1}p_kp_j$ ？{.quiz .fill}

因为 $A_i$ 的维数为 $p_{i-1} \times p_i$ ， $A_k$ 的维数为 $p_{k-1} \times p_k$ ， $A_j$ 的维数为 $p_{j-1} \times p_j$ ，所以 $A_iA_kA_j$ 的维数为 $p_{i-1} \times p_j$ ，所以需要 $p_{i-1}p_kp_j$ 次乘法

自底向上计算最优值

void MatrixChain(vector<int> &p, vector<vector<int>> &m,
                 vector<vector<int>> &s) {
  /**
    * p: 矩阵链的维数
    * m: 存储计算代价
    * s: 存储最优分割点
   */
  int n = p.size() - 1; // 矩阵链的长度
  for (int i = 1; i <= n; i++) {
    m[i][i] = 0; // 初始化对角线元素为0，因为单个矩阵的计算代价为0
  }
  for (int r = 2; r <= n; r++) { // r表示当前考虑的矩阵链的长度，从2到n
    for (int i = 1; i <= n - r + 1; i++) { // i表示矩阵链的起始位置
      int j = i + r - 1; // j表示矩阵链的结束位置
      m[i][j] = m[i + 1][j] + p[i - 1] * p[i] * p[j]; // 初始代价，假设最优分割点为i
      s[i][j] = i; // 记录最优分割点
      for (int k = i + 1; k < j; k++) { // 遍历所有可能的分割点
        int t = m[i][k] + m[k + 1][j] + p[i - 1] * p[k] * p[j]; // 计算当前分割点的代价
        if (t < m[i][j]) { // 如果当前代价小于已知最小代价
          m[i][j] = t; // 更新最小代价
          s[i][j] = k; // 更新最优分割点
        }
      }
    }
  }
}

构造最优解

void Traceback(vector<vector<int>> &s, int i, int j) {
  if (i == j) { // 如果i等于j，说明矩阵链中只有一个矩阵
    cout << "A" << i; // 输出矩阵的标识符
    return;
  }
  cout << "("; // 输出左括号表示开始一个新的矩阵链
  Traceback(s, i, s[i][j]); // 递归处理第一个子链
  Traceback(s, s[i][j] + 1, j); // 递归处理第二个子链
  cout << ")"; // 输出右括号表示结束一个矩阵链
}

最长公共子序列

子序列：一个给定序列的子序列是在该序列中删去若干元素后得到的序列。确切地说，若给定序列 $X=\{x_1,x_2,\cdots,x_m\}$ ，则另一个序列 $Z=\{z_1,z_2,\cdots,z_k\}$ 是 $X$ 的子序列是指存在一个严格递增的序列 $\{i_1,i_2,\cdots,i_k\}$ ，使得对于所有 $j=1,2,\cdots,k$ ，有 $z_j=x_{i_j}$ 。

最长公共子序列的结构

设序列 $X = \{x_1,x_2,\dots,x_m\}$ 和 $Y = \{y_1,y_2,\dots,y_n\}$ 的最长公共子序列为 $Z=\{z_1,z_2,\dots,z_k\}$ ，则

若 $x_m=y_n$ ，则 $z_k=x_m=y_n$ ，且 $Z_{k-1}$ 是 $X_{m-1}$ 和 $Y_{n-1}$ 的最长公共子序列
若 $x_m\neq y_n$ 且 $z_k\neq x_m$ ，则 $Z$ 是 $X_{m-1}$ 和 $Y$ 的最长公共子序列
若 $x_m\neq y_n$ 且 $z_k\neq y_n$ ，则 $Z$ 是 $X$ 和 $Y_{n-1}$ 的最长公共子序列

证明：

如果 $z_k\neq x_m$ ，那么可以将 $x_m=y_n$ 加入到 $Z$ 中，得到一个更长的公共子序列，与 $Z$ 的定义矛盾。因此必然有 $x_m=y_n=z_k$ 。由此可知， $Z_{k-1}$ 是 $X_{m-1}$ 和 $Y_{n-1}$ 的最长公共子序列。若 $X_{m-1}$ 和 $Y_{n-1}$ 有长度大于 $k-1$ 的公共子序列 $W$ ，则将 $x_m$ 加在 $W$ 的末尾，得到一个长度大于 $k$ 的公共子序列，与 $Z$ 的定义矛盾。
如果 $z_k\neq x_m$ ，那么 $Z$ 是 $X_{m-1}$ 和 $Y$ 的最长公共子序列。若 $X_{m-1}$ 和 $Y$ 有长度大于 $k$ 的公共子序列 $W$ ，那么 $W$ 也是 $X$ 和 $Y$ 的公共子序列，与 $Z$ 的定义矛盾。
同理， $Z$ 是 $X$ 和 $Y_{n-1}$ 的最长公共子序列。

子问题的递归结构

设 $c[i][j]$ 为 $X_i$ 和 $Y_j$ 的最长公共子序列的长度，则有

c[i][j]=\begin{cases} 0 & i=0\text{或}j=0\\ c[i-1][j-1]+1 & i,j>0\text{且}x_i=y_j\\ \max\{c[i][j-1],c[i-1][j]\} & i,j>0\text{且}x_i\neq y_j \end{cases}

计算最优值

void LCSLength(const string &X, const string &Y, vector<vector<int>> &c,
               vector<vector<string>> &b) {
  int m = X.size();
  int n = Y.size();
  // for (int i = 1; i <= m; i++) {
  //   c[i][0] = 0;
  // }
  // for (int j = 0; j <= n; j++) {
  //   c[0][j] = 0;
  // }
  for (int i = 1; i <= m; i++) {
    for (int j = 1; j <= n; j++) {
      if (X[i - 1] == Y[j - 1]) { // 注意这里的下标，因为X和Y的下标是从0开始的，所以要减1
        c[i][j] = c[i - 1][j - 1] + 1;
        b[i][j] = "↖";
      } else if (c[i - 1][j] >= c[i][j - 1]) {
        c[i][j] = c[i - 1][j];
        b[i][j] = "↑";
      } else {
        c[i][j] = c[i][j - 1];
        b[i][j] = "←";
      }
    }
  }
}

构建LCS

string LCS(const string &X, const string &Y, const vector<vector<string>> &b,
           int i, int j) {
  if (i == 0 || j == 0) {
    return "";
  }
  if (b[i][j] == "↖") {
    return LCS(X, Y, b, i - 1, j - 1) + X[i - 1];
  } else if (b[i][j] == "↑") {
    return LCS(X, Y, b, i - 1, j);
  } else {
    return LCS(X, Y, b, i, j - 1);
  }
}

↑和←只指引构造LCS的方向，不是LCS的一部分，只有↖才是LCS的一部分。

算法改进

省去b数组，直接构造LCS

string LCSWithoutB(const string &X, const string &Y) {
  int m = X.size();
  int n = Y.size();
  vector<vector<int>> c(m + 1, vector<int>(n + 1, 0));
  for (int i = 1; i <= m; i++) {
    for (int j = 1; j <= n; j++) {
      if (X[i - 1] == Y[j - 1]) {
        c[i][j] = c[i - 1][j - 1] + 1;
      } else {
        c[i][j] = max(c[i - 1][j], c[i][j - 1]);
      }
    }
  }
  string lcs;
  int i = m, j = n;
  while (i > 0 && j > 0) {
    if (X[i - 1] == Y[j - 1]) {
      lcs = X[i - 1] + lcs;
      i--;
      j--;
    } else if (c[i - 1][j] >= c[i][j - 1]) {
      i--;
    } else {
      j--;
    }
  }
  return lcs;
}

只计算LCS的长度，不构造LCS，仅用一维dp

int LCSLengthOnly(const string &X, const string &Y) {
  // m 保存字符串 X 的长度
  int m = X.size();
  // n 保存字符串 Y 的长度
  int n = Y.size();

  // 创建一个大小为 (n+1) 的一维数组 'c'，初始值为 0。
  // 该数组用于存储到目前为止，X 和 Y 每个位置的最长公共子序列长度。
  vector<int> c(n + 1, 0);

  // 遍历字符串 X 的每一个字符
  for (int i = 1; i <= m; i++) {
    // 'prev' 保存上一次 i 循环中 c[j-1] 的值 (上一行)
    int prev = 0;

    // 遍历字符串 Y 的每一个字符
    for (int j = 1; j <= n; j++) {
      // 'temp' 临时保存当前 c[j] 的值，在它被更新前
      int temp = c[j];

      // 如果字符相同，则当前位置的 LCS 长度增加 1
      if (X[i - 1] == Y[j - 1]) {
        c[j] = prev + 1;
      } else {
        // 如果字符不同，则取当前列和前一列的最大值
        c[j] = max(c[j], c[j - 1]);
      }
      // 更新 prev 为 c[j] 原来的值
      prev = temp;
    }
  }
  // 返回最终的 LCS 长度
  return c[n];
}

最大子段和

给定由 $n$ 个整数组成的序列 $a_1,a_2,\cdots,a_n$ ，求该序列形如 $\sum\limits_{k=i}^{j}a_k$ 的连续子段的最大和，当所有整数均为负数时，最大子段和为0。

定义dp[i]为 $\max\limits_{1\leq j\leq i}\sum\limits_{k=j}^{i}a_k$ ，即以 $1-i$ 为左端点，以 $i$ 为右端点的最大子段和。

当dp[i-1] >= 0时，dp[i] = dp[i-1] + a[i]，否则dp[i] = a[i]。

dp[i]=\begin{cases} 0 & i=0\\ \max\{dp[i-1]+a[i],a[i]\} & i\leq 1 \end{cases}


auto LSS(vector<int> a) {
  vector<int> dp(a.size() + 1);
  dp[0] = 0;
  for (int i = 1; i <= a.size(); i++) {
    dp[i] = max(dp[i - 1] + a[i - 1], a[i - 1]);
  }
  auto res = max_element(dp.begin(), dp.end());
  return *res;
}

// 状态压缩
auto LSS2(vector<int> a) {
  int dp = 0, res = 0;
  for (const auto &x: a) {
    dp = dp > 0 ? dp + x : x;
    res = max(res, dp);
  }
  return res;
}

凸多边形三角剖分

给定一个凸多边形以及定义在由多边形的边和弦组成的三角形上的权函数 $\omega$ ，将其分割成若干个三角形，使得分割后的三角形的总的权值和最小。

图 3

定义 $dp[i][j]$ 为凸子多边形 $\{v_{i-1}, v_i,\cdots, v_j\}$ 的最优三角剖分的权值和，

dp[i][j]=\begin{cases} 0 & j=i\\ \min\limits_{i<=k<j}\{dp[i][k]+dp[k+1][j]+\omega(v_{i-1},v_k,v_j)\} & j>i \end{cases}

void MinWeightTriangulation(vector<vector<double>> &dp, vector<vector<int>> &s) {
  int n = dp.size() - 2; // 边数 = 多边形的顶点数-1
  for (int i = 1; i <= n; i++) {
    dp[i][i] = 0;
  }
  for (int r = 2; r <= n; r++) {
    for (int i = 1; i <= n - r + 1; i++) {
      auto j = i + r - 1;
      dp[i][j] = dp[i + 1][j] + w(i - 1, i, j);
      s[i][j] = i;
      for (int k = i + 1; k < j; k++) {
        auto t = dp[i][k] + dp[k + 1][j] + w(i - 1, k, j);
        if (t < dp[i][j]) {
          dp[i][j] = t;
          s[i][j] = k;
        }
      }
    }
  }
}

图像压缩

数字化图像是 $n\times n$ 的像素阵列。假定每个像素有一个0~255的灰度值, 存储一个像素需8位。为了减少存储空间, 采用变长模式, 即不同像素用不同位数来存储。

将像素分成连续的 $m$ 段 $S_1,S_2,\cdots,S_m$ ，使每段中的像素存储位数相同。第 $i$ 段的存储像素数为l[i]，且该段中的每个像素只用b[i]表示。

存储空间为 $\sum\limits_{i=1}^{m}l[i]\times b[i]+11m$ ，其中11m为存储段的信息所需的位数。

图像压缩的最优子结构

设 $l[i],b[i],1\leq i\leq m$ 是 $\{p_1,p_2,\cdots,p_i\}$ 一个最优方案，显然 $l[1],b[1]$ 是 $\{p_1,\cdots,p_{l[1]}\}$ 的最优方案，且 $l[i], b[i], 2\leq i \leq m$ 是 $\{p_{l[i]+1},\cdots,p_{n}\}$ 的最优方案。

图像压缩的递归结构

设 $s[i]$ 为 $\{p_1,p_2,\cdots,p_i\}$ 的最优存储位数

考察最后一个元素 $p_i$ 的分段情况
假设 $p_i$ 自成一段，则 $S[i] = s[i-1] + \text{保存 } p_i \text{ 的代价}$ ；
假设最后 2 个像素点为一段，则 $s[i] = s[i-2] + \text{保存最后 2 个像素点的代价}$ ；
假设最后 $i$ 个像素点为一段，则 $s[i] = s[0] + \text{保存最后 } i \text{ 个像素点的代价}$ ；
取 $s[i]$ 为 $\min$ 时对应的元素个数。假设为 $k$ 。
此时，则 $S[i] = s[i-k] + \text{保存最后 } k \text{ 个像素的代价}$ ；
后者 $= k \times \max\{\text{k 个灰度值二进制位数}\} + 11$ ；
求解 $s[i-k]$ 即可；
考察最后一个像素点的分段情况，自成 1 段？后 2 个点？后 3 个点？……重复上述过程。

\begin{align*} &s[n] = \min\limits_{1\leq k\leq\min\{n,256\}}\{s[n-k]+k\times a\max(n-k+1,n)\}+11\\ &a\max(i,j) = \lceil\log_2(\max\limits_{i \leq k \leq j}\{p_k\} + 1)\rceil \end{align*}

l[i]：前i个像素点最后一段包含的个数。
b[i]：前i个像素点最后一段位数/最大值。
a[i]：第i个像素点的位数。

int length(int x) {
  int l = 1;
  x >>= 1;
  while (x > 0) {
    l++;
    x >>= 1;
  }
  return l;
}

void ImageCompression(vector<int> &p, vector<int> &l, vector<int> &b,
      vector<int> &s) {
  const int n = p.size();
  constexpr int L_MAX = 256, HEADER = 11; // 定义最大块长度和头部长度
  s[0] = 0;
  vector<int> a(n, 0);
  // 计算每个像素值的位数，存储在数组 a 中
  for (int i = 0; i < n; i++) { // 遍历所有像素
    a[i] = length(p[i]); // length() 函数计算 p[i] 的二进制位数
    int bMax = numeric_limits<int>::min(); // 初始化当前块中位数的最大值
    s[i] = numeric_limits<int>::max(); // 初始化 s[i] 为最大整数
    // 考虑从位置 i 向前的不同块大小 j
    for (int j = 1; j <= i + 1 && j <= L_MAX; j++) { // j 是当前块的长度
      // 更新当前块中像素位数的最大值
      bMax = max(bMax, a[i - j + 1]); // 在当前块中找到最大的位数
      // 计算将当前块划分为长度为 j 的块后的总存储位数，并与之前的最小值比较
      if (s[i] > s[i - j] + j * bMax) {
        s[i] = s[i - j] + j * bMax; // 更新最小存储位数
        l[i] = j; // 记录当前最优块的长度
        b[i] = bMax; // 记录当前最优块的位数
      }
    }
    s[i] += HEADER; // 加上存储段信息所需的位数
  }
}

电路布线

一块电路板的上下两端分别有 $n$ 个引脚，用导线 $(i, \pi(i))$ 连接引脚 $i$ 和 $\pi(i)$ ，其中 $\pi$ 是一个排列。第 $i$ 条连线和第 $j$ 条连线相交当且仅当 $\pi(i) > \pi(j)$ 且 $i < j$ 。要求确定导线集的最大不相交子集。

图 4

化为多步决策,自底向上,先求出只有一条连线的最大不相交子集,再求有2条连线的最大不相交子集…

电路布线的最优子结构

记 $N(i,j) = \{t|(t, \pi(t)) \in Nets, t \leq i, \pi(t) \leq j\}$ ， $N(i,j)$ 的最大不相交子集为 $MNS(i,j)$ ， $Size(i,j) = |MNS(i,j)|$ 。

当 $i = 1$ 时，有 $MNS(i,j) = N(1, j) = \begin{cases}\varnothing & j < \pi(1)\\ \{1, \pi(1)\} & j \geq \pi(1)\end{cases}$
当 $i > 1$ $i > 1$ 时，有
- 若 $j < \pi(i)$ 。此时 $(i, \pi(i)) \notin N(i,j)$ ，所以 $N(i,j) = N(i-1,j)$ ， $Size(i,j) = Size(i-1,j)$
- 若 $j \geq \pi(i)$ 。若 $(i, \pi(i)) \in MNS(i,j)$ ，则对任意 $(t, \pi(t)) \in MNS(i,j)$ ，有 $t < i$ ， $\pi(t) < \pi(i)$ ，否则 $(t, \pi(t))$ 和 $(i, \pi(i))$ 相交。所以 $MNS(i,j) - \{(i, \pi(i))\}$ 是 $N(i-1, \pi(i)-1)$ 的最大不相交子集，否则 $MNS(i-1, \pi(i)-1)\cup\{(i, \pi(i))\} \subseteq N(i,j)$ 是比 $MNS(i,j)$ 更大的不相交子集，这与 $MNS(i,j)$ 的定义矛盾。若 $(i, \pi(i)) \notin MNS(i,j)$ ，则对任意 $(t, \pi(t)) \in MNS(i,j)$ ，有 $t < i$ ，从而 $MNS(i,j)/subseteq N(i-1,j)$ ，因此 $Size(i,j) /leq Size(i-1,j)$ 。另一方面， $MNS(i-1,j) \subseteq N(i,j)$ ，所以 $Size(i,j) \geq Size(i-1,j)$ ，则 $Size(i,j) = Size(i-1,j)$ 。

递归计算最优值

当 $i = 1$ 时， $Size(1,j) = \begin{cases}0 & j < \pi(1)\\ 1 & j \geq \pi(1)\end{cases}$
当 $i > 1$ 时， $Size(i,j) = \begin{cases}Size(i-1,j) & j < \pi(i)\\ \max\{Size(i-1,j), Size(i-1, \pi(i)-1)+1\} & j \geq \pi(i)\end{cases}$

// C[0:n]
void MNS(const vector<int> &C, vector<vector<int>> &size) {
  const int n = C.size();
  for (int j = 0; j < n; j++) {
    size[0][j] = j < C[0] ? 0 : 1;
  }
  for (int i = 1; i < n - 1; i++) {
    for (int j = 0; j < n; j++) {
      if (j < C[i]) {
        size[i][j] = size[i - 1][j];
      } else {
        size[i][j] = max(size[i - 1][j], size[i - 1][C[i] - 1] + 1);
      }
    }
  }
  size[n - 1][n - 1] = max(size[n - 2][n - 1], size[n - 2][C[n - 1] - 1] + 1);
}

构造最优解

auto Traceback(const vector<vector<int>> &size, const vector<int> &C) {
  vector<int> Net;
  int j = C.size() - 1;
  int m = 0;
  for (int i = C.size() - 1; i > 0; i--) {
    if (size[i][j] != size[i - 1][j]) {
      Net[m++] = i;
      j = C[i] - 1;
    }

  }if (j >= C[0]) {
      Net[m++] = 0;
    }
  return Net;
}

流水线作业调度

$n$ 个作业 $\{1,2,\cdots,n\}$ 要在2台相同的流水线上加工，每个作业加工顺序为先在 $M_1$ 上加工，再在 $M_2$ 上加工。第 $i$ 个作业在 $M_1$ 上加工时间为 $a_i$ ，在 $M_2$ 上加工时间为 $b_i$ 。

最优调度方案是使得 $M_1$ 没有空闲时间， $M_2$ 的空闲时间最小。

设全部作业集合为 $N = \{1,2,\cdots,n\}$ ， $S \subseteq N$ 是一个作业子集。在一般情况下，机器 $M_1$ 开始加工 $S$ 中作业时，机器 $M_2$ 还在加工其他作业，要等时间 $t$ 后才可利用。这种情况下完成 $S$ 中作业所需的最短时间记为 $T(S, t)$ 。
流水作业调度问题的最优值为 $T(N, 0)$ 。

流水线作业调度的最优子结构

设 $\pi$ 是所给 $n$ 个作业的一个最优调度方案，所需加工时间为 $a_{\pi(1)} + T'$ 。其中 $T'$ 是在机器 $M_2$ 的等待时间为 $b_{\pi(1)}$ 时，安排作业 $\pi(2),\pi(3),\cdots,\pi(n)$ 所需的时间。记 $S=N-\{\pi(1)\}$ ，则 $T' = T(S, b_{\pi(1)})$ 。

流水线作业调度的递归计算最优值

$T(N, 0) = \min\limits_{1\leq i\leq n}\{a_i + T(N-\{i\}, b_i)\}$ ，推广到一般情况有：

T(S,t) = \min \limits_{i \in S} \{a_i+T(S-\{i\}, b_i+max\{t-a_i,0\})\}

式中， $\max\{t-a_i, 0\}$ 项是由于在机器 $M_2$ 上，作业i必须在 $\max\{t,a_i\}$ 时间之后才能开工。因此在机器 $M_1$ 上完成作业i之后在机器上还需要 $b_i+\max\{t,a_i\} - a_i = b_i + \max\{t-a_i, 0\}$ 时间才能完成对作业i的加工。

流水线作业调度的Johnson法则

如果作业 $i$ 和作业 $j$ 满足 $\min\{b_i, a_j\} \geq \min\{b_j, a_i\}$ ，则作业 $i$ 应该在作业 $j$ 之前加工。

$n$ 个任务的Johnson法则

令 $N_1 = \{i|a_i < b_i\}$ ， $N_2 = \{i|a_i \geq b_i\}$ ；
按照 $a_i$ 的非降序排列 $N_1$ 中的任务，按照 $b_i$ 的非升序排列 $N_2$ 中的任务；
$N_1$ 中的任务在 $N_2$ 中的任务之前加工。

vector<int> flowShop(const vector<int> &a, const vector<int> &b) {
  const int n = a.size();
  vector<int> C(n);
  vector<pair<int, int>> tasks(n);
  for (int i = 0; i < n; i++) {
    tasks[i] = {a[i], b[i]};
  }
  vector<int> N1, N2;
  for (int i = 0; i < n; i++) {
    if (tasks[i].first < tasks[i].second) {
      N1.push_back(i);
    } else {
      N2.push_back(i);
    }
  }
  sort(N1.begin(), N1.end(),
       [&](int i, int j) { return tasks[i].first < tasks[j].first; });
  sort(N2.begin(), N2.end(),
       [&](int i, int j) { return tasks[i].second > tasks[j].second; });
  move(N1.begin(), N1.end(), C.begin());
  move(N2.begin(), N2.end(), C.begin() + N1.size());
  return C;
}

流水线作业调度的总时间

int calculateTime(vector<int> C, const vector<int> &a, const vector<int> &b) {
    const int n = C.size();
    vector<int> f(n);
    vector<int> g(n);
    f[0] = a[C[0]];
    g[0] = f[0] + b[C[0]];
    for (int i = 1; i < n; i++) {
        f[i] = f[i - 1] + a[C[i]];
        g[i] = max(g[i - 1], f[i]) + b[C[i]];
    }
    return g[n - 1];
}

0-1背包问题

给定 $n$ 个物品，每个物品的重量为 $w_i$ ，价值为 $v_i$ ，背包的容量为 $c$ ，求如何装入背包使得背包中物品的总价值最大。

形式化描述为：给定 $c>0, w_i>0, v_i>0, i=1,2,\cdots,n$ ，求一个向量 $x=(x_1,x_2,\cdots,x_n)$ ，其中 $x_i\in\{0,1\}$ ，使得 $\sum\limits_{i=1}^{n}w_ix_i\leq c$ 且 $\sum\limits_{i=1}^{n}v_ix_i$ 最大，即

\begin{cases} \max & \sum\limits_{i=1}^{n}v_ix_i\\ s.t. & \sum\limits_{i=1}^{n}w_ix_i\leq c\\ & x_i\in\{0,1\} & i=1,2,\cdots,n \end{cases}

0-1背包问题的最优子结构

设 $(y_1,y_2,\cdots,y_n)$ 是一个最优解，则 $(y_2,y_3,\cdots,y_n)$ 是下面相应子问题的一个最优解：

\begin{cases} \max & \sum\limits_{i=2}^{n}v_ix_i\\ s.t. & \sum\limits_{i=2}^{n}w_ix_i\leq c-w_iy_1\\ & x_i\in\{0,1\} & i=2,3,\cdots,n \end{cases}

否则，设 $(z_2,z_3,\cdots,z_n)$ 是上述子问题的一个最优解，则 $(y_2,y_3,\cdots,y_n)$ 不是它的一个最优解。由此可知， $\sum\limits_{i=2}^{n}v_iz_i > \sum\limits_{i=2}^{n}v_iy_i$ ，且 $w_1y_1 + \sum\limits_{i=2}^{n}w_iz_i \leq c$ 。因此

\begin{align*} v_1y_1 + \sum\limits_{i=2}^{n}v_iz_i &> \sum\limits_{i=1}^{n}v_iy_i \\ w_1y_1 + \sum\limits_{i=2}^{n}w_iz_i &\leq c \end{align*}

这说明 $(y_1,z_2,z_3,\cdots,z_n)$ 是原问题的一个最优解。从而 $(y_1,y_2,\cdots,y_n)$ 不是原问题的一个最优解，这与假设矛盾。

0-1背包问题的递归计算最优值

设所给0-1背包的子问题的最优值为 $m(i, j)$ ，即可选择物品为 $\{i, i+1,\cdots,n\}$ ，背包容量为 $j$ 时的最优值。则有

m(i, j) = \begin{cases} max\{m(i+1, j), m(i+1, j-w_i)+v_i\} & j\geq w_i\\ m(i+1, j) & j < w_i \end{cases}

// 下标从1开始
void knapsack(const vector<int> &w, const vector<int> &v, int c,
              vector<vector<int>> &m) {
  const int n = w.size();
  for (int j = 0; j <= min(c, w[n - 1]); j++) {
    m[n][j] = 0;
  }
  for (int j = w[n]; j <= c; j++) {
    m[n][j] = v[n];
  }
  for (int i = n - 1; i > 1; i--) {
    for (int j = 0; j <= min(c, w[i - 1]); j++) {
      m[i][j] = m[i + 1][j];
    }
    for (int j = w[i]; j <= c; j++) {
      m[i][j] = max(m[i + 1][j], m[i + 1][j - w[i]] + v[i]);
    }
  }
  if (c >= w[1]) {
    m[1][c] = max(m[1][c], m[2][c - w[1]] + v[1]);
  }
  else {
    m[1][c] = m[2][c];
  }
}

void Traceback(const vector<vector<int>> &m, const vector<int> &w,
               const vector<int> &v, int c, vector<int> &x) {
  const int n = w.size();
  for (int i = 1; i < n; i++) {
    if (m[i][c] == m[i + 1][c]) {
      x[i] = 0;
    } else {
      x[i] = 1;
      c -= w[i];
    }
  }
  x[n] = m[n][c] > 0 ? 1 : 0;
}

0-1背包问题的跳跃点解法

$p[i] = \{(j, m(i, j))|0\leq j\leq c\}$ ， $p[i]$ 是一个有序对的集合，其中 $j$ 是背包容量， $m(i, j)$ 是选择物品 $\{i, i+1,\cdots,n\}$ ，背包容量为 $j$ 时的最优值。

$m(i,j)$ 的全部跳跃点 $p[i]$ 包含于 $m(i+1,j)$ 的跳跃点集 $p[i+1]$ 与 $m(i+1,j-w_i)+v_i$ 的跳跃点集 $q[i+1]$ 的并集中

\begin{align*} p[i] &\subseteq p[i+1] \cup q[i+1]\\ q[i+1] &= p[i+1] \oplus (w_i, v_i) \\ &= \{(j+w_i, m(i, j)+v_i) \mid (j, m(i, j)) \in p[i+1]\} \end{align*}

设 $(a,b)$ 和 $(c,d)$ 是 $p[i+1] \cup q[i+1]$ 中的两个跳跃点，当 $c \geq a$ 且 $d < b$ 时， $(c, d)$ 是 $(a, b)$ 的一个受控点，需要删掉。

图 5

图中 $(5,4)$ 是 $(4,6)$ 的一个受控点，需要删掉。

贪心算法

活动安排问题

设有 $n$ 个活动的集合 $E=\{1,2,\cdots,n\}$ ，每个活动 $i$ 都有一个使用该资源的起始时间 $s_i$ 和一个结束时间 $f_i$ ，且 $0\leq s_i < f_i < \infty$ 。如果选择活动 $i$ ，则活动 $i$ 发生在半开时间区间 $[s_i, f_i)$ 内。若区间 $[s_i, f_i)$ 与 $[s_j, f_j)$ 不相交，则称活动 $i$ 与活动 $j$ 是相容的。目标：找出最大相容活动集。

思路：选择最早结束的活动，然后删除与该活动相容的活动，重复此过程。

class Activity {
public:
  int id;
  int start;
  int finish;
  Activity(int s, int f) : start(s), finish(f) {
    static int count = 0;
    id = count++;
  }
};

void GreedyActivitySelector(vector<shared_ptr<Activity>> &activities,
                            vector<shared_ptr<Activity>> &selected) {

  ranges::sort(activities, [](const shared_ptr<Activity> &a,
                              const shared_ptr<Activity> &b) {
    return a->finish < b->finish;
  });
  selected.clear();
  selected.emplace_back(activities[0]);
  auto last = activities[0];
  for (int i = 1; i < activities.size(); i++) {
    if (activities[i]->start >= last->finish) {
      selected.emplace_back(activities[i]);
      last = activities[i];
    }
  }
}

证明活动安排问题的贪心选择性质

证明活动安排问题有一个最优解以贪心选择开始

设 $A$ 是最优解，且 $A$ 中活动也按 $f_i$ 非减序排列， $A$ 中第一个活动是 $k$ 。

若 $k=1$ ，则 $A$ 就是一个以贪心选择开始的最优解；

否则，构造 $B=A-\{k\}\cup \{1\}$

证明每一步贪心选择→问题的整体最优解

若 $A$ 是 $E$ 的最优解，则 $A' = A - \{1\}$ 是 $E' = \{i\in E|s_i \geq f_1\}$ 的最优解。

如果能找到一个 $E'$ 的解 $B'$ ，它包含比 $A'$ 更多的活动，则 $B = B' \cup \{1\}$ 优于 $A$ ，这与 $A$ 是最优解矛盾。

贪心算法基本要素

贪心算法通过一系列的选择来得到问题的解。它所做的每一个选择都是当前状态下局部的最好选择，即贪心选择。

最优子结构性质
贪心选择性质

贪心与动态规划的区别

动态规划算法通常以自底向上的方式解决问题，每步所作的选择依赖于相关子问题的解。
贪心算法通常以自顶向下的方式解决问题，贪心选择依赖于以往作出的选择，不依赖于子问题的解。

贪心选择思路

证明每一步贪心选择→问题的整体最优解

假设问题有一个整体最优解，并证明可修改这个最优解，使其以贪心选择开始。做了贪心选择后，原问题简化为规模更小的类似子问题。
运用数学归纳法证明：每一步贪心选择→问题的整体最优解。

背包问题（可选部分）

贪心选择性质：每次选择单位价值最高的物品。可选部分。

class Item {
public:
  int id;
  int weight;
  int value;
  double unitValue;
  Item(int w, int v) : weight(w), value(v) {
    static int count = 0;
    id = count++;
    unitValue = static_cast<double>(v) / w;
  }
};

void FractionalKnapsack(vector<shared_ptr<Item>> &items, int c,
                        vector<shared_ptr<Item>> &selected) {
  ranges::sort(items, [](const shared_ptr<Item> &a, const shared_ptr<Item> &b) {
    return a->unitValue > b->unitValue;
  });
  selected.clear();
  int weight = 0;
  for (int i = 0; i < items.size(); i++) {
    if (weight + items[i]->weight <= c) {
      selected.emplace_back(items[i]);
      weight += items[i]->weight;
    } else {
      auto remain = c - weight;
      auto item = make_shared<Item>(remain, remain * items[i]->unitValue);
      selected.emplace_back(item);
      break;
    }
  }
}

最优装载

有一批集装箱要装上一艘载重量为 $C$ 的轮船，其中第 $i$ 个集装箱的重量为 $w_i$ 。装载问题是找出尽可能多的集装箱装上轮船。

形式化描述为

\begin{cases} \max & \sum\limits_{i=1}^{n}x_i\\ s.t. & \sum\limits_{i=1}^{n}w_ix_i \leq C\\ & x_i\in\{0,1\} & i=1,2,\cdots,n \end{cases}

贪心选择性质：每次选择重量最小的集装箱。

vector<int> Loading(vector<int> &w, int c) {
  vector<int> x(w.size());
  ranges::sort(w);
  int weight = 0;
  for (int i = 0; i < w.size(); i++) {
    if (weight + w[i] <= c) {
      x.emplace_back(w[i]);
      weight += w[i];
    }
  }
  return x;
}

哈夫曼编码

给定编码字符集 $c$ ，以及每个字符的频率 $f(c)$ ，构造一个无歧义的前缀编码，使得所有字符的编码长度之和最小。
平均码长： $B(T) = \sum\limits_{c\in C}f(c)d_T(c)$ ，其中 $d_T(c)$ 是字符 $c$ 在树 $T$ 中的深度。
找到使 $B(T)$ 最小的前缀码编码方案。

哈夫曼编码的思路

优先队列 $Q$ 以 $f(c)$ 为关键字存放二叉树各节点，每次从 $Q$ 中选取两个频率最小的二叉树合并，然后将新树（根节点的频率为两个子树的频率之和）插入 $Q$ 。

class Node {
public:
  char ch;
  int freq;
  shared_ptr<Node> left;
  shared_ptr<Node> right;
  Node(char c, int f) : ch(c), freq(f) {}
};

shared_ptr<Node> Huffman(vector<pair<char, int>> &freq) {
  auto cmp = [](const shared_ptr<Node> &a, const shared_ptr<Node> &b) {
    return a->freq > b->freq;
  };
  priority_queue<shared_ptr<Node>, vector<shared_ptr<Node>>, decltype(cmp)> Q(cmp);
  for (const auto &p : freq) {
    Q.emplace(make_shared<Node>(p.first, p.second));
  }
  while (Q.size() > 1) {
    auto left = Q.top();
    Q.pop();
    auto right = Q.top();
    Q.pop();
    auto parent = make_shared<Node>('\0', left->freq + right->freq);
    parent->left = left;
    parent->right = right;
    Q.emplace(parent);
  }
  return Q.top();
}

哈夫曼编码的正确性

哈夫曼编码的贪心选择性质

设 $x$ 和 $y$ 是字符集 $C$ 中具有最小频率的两个字符，证明存在 $C$ 的最优前缀码使 $x$ 和 $y$ 具有最长、相同的码长且仅最后一位编码不同。
证明：设二叉树 $T$ 表示 $C$ 的任意一个最优前缀码方案。只要证明可以对 $T$ 做适当修改后，得到一棵新的二叉树 $T'$ ，新树中， $x$ 和 $y$ 是最深叶子且为兄弟。
同时，新树也是 $C$ 的最优前缀码方案。

\begin{align*} B(T) - B(T') &= \sum\limits_{c\in C}f(c)d_T(c) - \sum\limits_{c\in C}f(c)d_{T'}(c)\\ &= f(x)d_T(x) + f(b)d_T(b) - f(x)d_{T'}(x) - f(b)d_{T'}(b)\\ &= f(x)d_T(x) + f(b)d_T(b) - f(x)d_{T}(b) - f(b)d_{T}(x)\\ &= (f(b) - f(x))(d_T(b) - d_T(x)) \geq 0 \end{align*}

同理， $B(T') - B(T'') \geq 0$ ，所以 $B(T) \geq B(T') \geq B(T'')$ ，又因为 $T$ 是最优前缀码方案，所以 $B(T) = B(T')$ ，所以 $T'$ 也是最优前缀码方案。

哈夫曼编码的最优子结构性质

设 $T$ 表示 $C$ 的一个最优前缀码方案。 $x$ 和 $y$ 是树 $T$ 中的叶子节点且为兄弟。 $z$ 是它们的父亲。

若将 $z$ 看做是具有频率 $f(z)=f(x)+f(y)$ 的字符，

则证明树 $T'=T-\{x,y\}$ 表示字符集 $C'=C-\{x,y\} \cup \{z\}$ 的一个最优前缀码即可。

证明：首先证明 $T$ 的平均码长 $B(T)$ 可用 $B(T')$ 表示。
对任意字符 $c\in C-\{x,y\}$ ，有 $d_{T}(c) = d_{T'}(c)$ ，故 $f(c)d_{T}(c) = f(c)d_{T'}(c)$ 。
另一方面， $d_{T}(x) = d_T(y) = d_{T'}(z) + 1$ ，
故

\begin{align*} f(x)d_{T}(x) + f(y)d_{T}(y) &= (f(x)+f(y))(d_{T'}(z)+1) \\ &=f(x) + f(y)f(z)d_{T'}(z) \end{align*}

若 $T'$ 不是 $C'$ 的最优前缀码方案，则存在另一棵树 $T''$ ，使得 $B(T'') < B(T')$ 。由于 $z$ 被看作 $C'$ 中的一个字符，故 $z$ 在 $T''$ 中是一个叶子节点，若将 $x$ 和 $y$ 加入树 $T''$ ，则得到一个新树 $T'''$ ，且有

\begin{align*} B(T''') &= B(T'') + f(x) + f(y) \\ &< B(T') + f(x) + f(y) = B(T) \end{align*}

这与 $T$ 是最优前缀码方案矛盾，所以 $T'$ 是 $C'$ 的最优前缀码方案。

回溯法

问题的解空间树

解空间树是一个有根树，其每个节点对应于问题的一个解，树的根节点对应于问题的初始状态，叶节点对应于问题的一个解。

回溯法的基本思想

回溯法从根结点出发，以深度优先的方式搜索解空间树。

[活结点]{.yellow}：自身已生成但其儿子还没有全部生成
[扩展结点]{.green}：正在产生其儿子的结点
[死结点]{.purple}：不满足约束条件或所有儿子已经产生的，不能向纵深方向移动的结点

回溯法的步骤

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

回溯法的解空间树构造

子集树

当所给问题是从 $n$ 个元素的集合 $S$ 中找出满足某种性质的子集时，解空间树是一个有根树，其每个节点对应于 $S$ 的一个子集。

满足所有约束条件的解状态结点称为回答结点。

排列树

当所给问题是从 $n$ 个元素的集合 $S$ 中找出满足某种性质的排列时，解空间树是一个有根树，其每个节点对应于 $S$ 的一个排列。

树中从根至叶结点的路径的集合构成解空间。树的每一个叶结点称为一个解状态。

解空间树的剪枝策略

用约束函数在扩展结点处剪去不满足约束的子树；
用限界函数剪去得不到最优解的子树。

回溯法的递归回溯

子集树的回溯法

// t表示当前扩展结点的深度
void Backtrack(int t) {
  if (t > n) {
    Output(x);
  } else {
    // f(n,t),g(n,t)分别表示在当前扩展结点处未搜索过的
    // 子树的起始编号和终止编号
    for (int i = f(n, t); i <= g(n, t); i++) {
      // h(i)表示在当前扩展节点处x[t]的第i个可选值
      x[t] = h(i);
      // Constraint(t)和Bound(t)表示当前扩展节点处
      // 的约束函数和限界函数
      if (Constraint(t) && Bound(t)) {
        Backtrack(t + 1);
      }
    }
  }
}

排列树的回溯法

// 调用Backtrack(1)开始搜索前，需要初始化x[1:n]为1:n
void Backtrack(int t) {
  if (t > n) {
    Output(x);
  } else {
    for (int i = t; i <= n; i++) {
      swap(x[t], x[i]);
      if (Constraint(t) && Bound(t)) {
        Backtrack(t + 1);
      }
      swap(x[t], x[i]);
    }
  }
}

回溯法的迭代回溯

void IterativeBacktrack() {
  int t = 1;
  while (t > 0) {
    if (f(n, t) <= g(n, t)) {
      for (int i = f(n, t); i <= g(n, t); i++) {
        x[t] = h(i);
        if (Constraint(t) && Bound(t)) {
          if (Solution(t)) {
            Output(x);
          } else {
            t++;
          }
        }
      }
    } else {
      t--;
    }
  }
}

旅行商问题

某旅行商要访问 $n$ 个城市，从城市 $1$ 出发，经过每个城市一次，最后回到城市 $1$ 。每两个城市之间有一条道路，旅行商要选择一条路径，使得总路程最短。

旅行商问题的解空间树

旅行商问题的解空间树是一个有根树，从根节点出发到叶节点的路径对应于旅行商的一条路径。

装载问题

$n$ 个集装箱要装上2艘载重量分别为 $C_1$ 和 $C_2$ 的轮船，其中第 $i$ 个集装箱的重量为 $w_i$ 。装载问题是找出尽可能多的集装箱装上轮船。

若装载问题有解, 采用如下策略可得一个最优装载方案:

将第一艘轮船尽可能装满;
剩余的货箱装到第二艘轮船上。

将第一艘船尽可能装满等价于如下0-l背包问题:

\begin{cases} \max & \sum\limits_{i=1}^{n}x_i\\ s.t. & \sum\limits_{i=1}^{n}w_ix_i \leq C_1\\ & x_i\in\{0,1\} & i=1,2,\cdots,n \end{cases}

装载问题的算法设计

template <typename T>
class Loading {
  private:
    void Backtrack(int i);
    vector<T> w; // 集装箱重量
    T c; // 轮船载重量
    T cw; // 当前载重量
    T bestw; // 当前最优载重量
  public:
    Loading() : cw(0), bestw(0) {}
    Loading(const vector<T> &ww, const T cc) : w(ww), c(cc), cw(0), bestw(0) {}
};

template <typename T>
void Loading<T>::Backtrack(int i) {
  if (i > w.size()) {
    bestw = max(bestw, cw);
    return;
  }
  // 搜索子树
  if (cw + w[i] <= c) {// 左子树(装入第i个集装箱)
    cw += w[i];
    Backtrack(i + 1);
    cw -= w[i];
  }
  // 右子树(不装入第i个集装箱)

  Backtrack(i + 1);

}

template <typename T>
T MaxLoading(const vector<T> w, const T c) {
  Loading<T> X(w, c);
  X.Backtrack(1);
  return X.bestw;
}

上界函数-解决右子树剪枝问题

template <typename T>
class Loading {
  private:
    void Backtrack(int i);
    vector<T> w; // 集装箱重量
    T c; // 轮船载重量
    T cw; // 当前载重量
    T bestw; // 当前最优载重量
    T r; // 剩余集装箱重量
  public:
    Loading() : cw(0), bestw(0) {}
    Loading(const vector<T> &ww, const T cc) : w(ww), c(cc), cw(0), bestw(0) {
      r = accumulate(w.begin(), w.end(), 0);
    }
};

template <typename T>
void Loading<T>::Backtrack(int i) {
  if (i > w.size()) {
    bestw = cw;
    return;
  }
  // 计算剩余集装箱重量
  r -= w[i];
  if (cw + w[i] <= c && cw + r > bestw) {// 左子树(装入第i个集装箱)
    cw += w[i];
    Backtrack(i + 1);
    cw -= w[i];
  }
  if (cw + r > bestw) {// 右子树(不装入第i个集装箱)
    Backtrack(i + 1);
  }
  r += w[i];
}

template <typename T>
T MaxLoading(const vector<T> w, const T c) {
  Loading<T> X(w, c);
  X.Backtrack(1);
  return X.bestw;
}

构造最优解-装载问题的回溯算法

template <typename T>
class Loading {
  private:
    void Backtrack(int i);
    vector<int> x; // 当前解
    vector<int> bestx; // 当前最优解
    vector<T> w; // 集装箱重量
    T c; // 轮船载重量
    T cw; // 当前载重量
    T bestw; // 当前最优载重量
    T r; // 剩余集装箱重量

  public:
    Loading() : cw(0), bestw(0) {}
    Loading(const vector<T> &ww, const T cc) : w(ww), c(cc), cw(0), bestw(0) {
      r = accumulate(w.begin(), w.end(), 0);
      x.resize(w.size() + 1);
      bestx.resize(w.size() + 1);
    }
};

template <typename T>
void Loading<T>::Backtrack(int i) {
  if (i > w.size()) {
    if (cw > bestw) {
      for (int j = 1; j <= w.size(); j++) {
        bestx[j] = x[j];
      }
      bestw = cw;
    }
    return;
  }
  r -= w[i];
  if (cw + w[i] <= c && cw + r > bestw) {
    x[i] = 1;
    cw += w[i];
    Backtrack(i + 1);
    cw -= w[i];
  }
  if (cw + r > bestw) {
    x[i] = 0;
    Backtrack(i + 1);
  }
  r += w[i];
}

template <typename T>
vector<int> MaxLoading(const vector<T> w, const T c) {
  Loading<T> X(w, c);
  X.Backtrack(1);
  return X.bestx;
}

0/1背包问题

给定 $n$ 个物品，每个物品的重量为 $w_i$ ，价值为 $v_i$ ，背包的容量为 $c$ ，求如何装入背包使得背包中物品的总价值最大。

0-1背包问题属于找最优解问题，适合于用子集树表示0-1背包问题的解空间。在搜索解空间树时

只要左儿子节点是一个可行结点，搜索就进入左子树。(约束剪枝) $\sum\limits_{i=1}^{n}w_ix_i \leq c$
- 在右子树中有可能包含最优解是才进入右子树搜索，否则将右子树剪去（限界剪枝）。

限界函数

设当前位于状态空间树的结点 $X$ 处，已考察 $k$ 个物品。

背包中的当前物品总重量为 $cw$ ，背包中的当前物品总价值为 $cp$ 。

背包的载重量为 $c$ ，则剩余载重是 $c - cw$ 。

使用贪心法，计算以剩余载重和剩余物品构成的一般背包问题的最优解值，设该最大收益为 $rp$ 。

$bp = cp + rp$ ，作为以 $X$ 为根的子树上所有可能的答案结点的目标函数值的上界。

0/1背包问题的回溯算法

void Backtrack(int i) {
  if (i > n) {
    bestp = cp;
  }
  if (cw + w[i] <= c) { // 左子树
    cw += w[i];
    cp += p[i];
    Backtrack(i + 1);
    cw -= w[i];
    cp -= p[i];
  }
  if (Bound(i + 1) > bestp) { // 右子树
    Backtrack(i + 1);
  }
}

int Bound(int i) {
  int cleft = c - cw;
  int b = cp;
  // 以物品单位价值递减的顺序装入物品（已经排序完成）
  while (i <= n && w[i] <= cleft) {
    cleft -= w[i];
    b += p[i];
    i++;
  }
  if (i <= n) { // 装入部分物品
    b += p[i] / w[i] * cleft;
  }
  return b;
}

最大团问题

给定无向图 $G=(V,E)$ ，如果 $U \subseteq V$ ，且对任意 $u,v \in U$ ， $(u,v) \in E$ ，则称 $U$ 是图 $G$ 的完全子图。 $G$ 的完全子图 $U$ 是 $G$ 的一个团当且仅当 $U$ 不包含在 $G$ 的更大的完全子图中。 $G$ 的最大团是指 $G$ 中所含顶点数最多的团。

在图中的无向图 $G$ 中，子集 $\{1,2\}$ 是 $G$ 的大小为 2 的完全子图。这个完全子图不是团，因为它被 $G$ 的更大的完全子图 $\{1,2,5\}$ 包含。 $\{1,2,5\}$ 是 $G$ 的最大团。 $\{1,4,5\}$ 和 $\{2,3,5\}$ 也是 $G$ 的最大团。

如果 $U \subseteq V$ ，且对任意 $u,v \in U$ ， $(u,v) \notin E$ ，则称 $U$ 是图 $G$ 的空子图。 $G$ 的空子图 $U$ 是 $G$ 的一个独立集当且仅当 $U$ 不包含在 $G$ 的更大的空子图中。 $G$ 的最大独立集是指 $G$ 中所含顶点数最多的独立集。

对于任意无向图 $G$ ，其补图 $\overline{G} = (V_1, E_1)$ 定义为 $V_1 = V$ ， $E_1 = \{(u,v) | u,v \in V, (u,v) \notin E\}$ 。 $G$ 的最大独立集是 $\overline{G}$ 的最大团。

最大团问题的算法设计

可以用子集树表示问题的解空间。解最大团问题的回溯法与解装载问题的回溯法十分相似。设当前扩展结点Z位于解空间树的第i层。在进入左子树前，必须确认从顶点i到已选入的顶点集中每个顶点都有边相连。在进入右子树前，必须确认还有足够多的可选择顶点，使得算法有可能在右子树中找到更大的团。
整型数组v返回所找到的最大团。v[i]=1当且仅当顶点i属于找到的最大团。

class Clique {
  private:
    vector<vector<int>> a; // 图的邻接矩阵
    vector<int> x; // 当前解
    int cn; // 当前团的顶点数
    int bestn; // 当前最优团的顶点数
    int n; // 图的顶点数
  public:
    void Backtrack(int i);
    Clique() : cn(0), bestn(0) {}
    Clique(const vector<vector<int>> &aa) : a(aa), n(aa.size()) {
      x.resize(n + 1);
      bestx.resize(n + 1);
    }
    vector<int> bestx; // 当前最优解
};

void Clique::Backtrack(int i) {
  if (i > n) {
    for (int j = 1; j <= n; j++) {
      bestx[j] = x[j];
    }
    bestn = cn;
    return;
  }
  bool ok = true;
  for (int j = 1; j < i; j++) {
    if (x[j] && !a[i][j]) {
      ok = false;
      break;
    }
  }
  if (ok) {
    x[i] = 1;
    cn++;
    Backtrack(i + 1);
    x[i] = 0;
    cn--;
  }
  if (cn + n - i > bestn) {
    x[i] = 0;
    Backtrack(i + 1);
  }
}

vector<int> MaxClique(const vector<vector<int>> &a) {
  Clique X(a);
  X.Backtrack(1);
  return X.bestx;
}

图的着色

给定无向连通图 $G$ 和 $m$ 种不同的颜色。用这些颜色为图 $G$ 的各顶点着色，每个顶点着一种颜色。是否有一种着色法，使 $G$ 中每条边的 $2$ 个顶点着有不同颜色？这个问题是图的 $m$ 可着色判定问题。若一个图最少需要 $m$ 种颜色才能使图中每条边连接的 $2$ 个顶点着不同颜色，则称这个数 $m$ 为该图的色数。求一个图的色数 $m$ 的问题称为图的 $m$ 可着色优化问题。

如果一个图的所有顶点和边都能用某种方式画在平面上且没有任何两边相交，则称这个图是可平面图。著名的平面图的四色猜想是图的 $m$ 可着色性判定问题的特殊情形。

图的着色问题的算法设计

采用 $n$ -元组 $(x_0, x_1, \dots, x_{n-1})$ 表示图 $G$ 的 $m$ -着色判定问题的解，并采用邻接矩阵表示无向图 $G=(V,E)$ 。

a[i][j] = \begin{cases} 1 & \text{如果} (i,j) \in E\\ 0 & \text{其他} \end{cases}

显式约束： $n$ -元组 $(x_0, x_1, \dots, x_{n-1})$ ， $x_i \in \{1，\dots，m\}$ ， $0 \leq i < n$ ，表示结点 $i$ 的颜色。 $x_i=0$ 表示没有可用的颜色。因此解空间的大小为 $m^n$ 。
隐式约束：如果边 $(i,j) \in E$ ，则 $x_i \ne x_j$ 。

约束函数：对所有 $i$ 和 $j$ ， $0 \leq i,j < k$ ， $i \neq j$ ，若 $a[i][j]=1$ ，则 $x_i \neq x_j$ 。（ $1 \leq x_i,x_j \leq m$ ）

限界函数：对于当前解 $(x_0, x_1, \dots, x_{n-1})$ ，如果已经着色的顶点数为 $k$ ，则剩余未着色的顶点数为 $n-k$ ，则最多需要 $m-k$ 种颜色。如果 $m-k=0$ ，则当前解是可行解，否则当前解是一个可行解的上界。

class Color {
private:
    bool Ok(int k);
    vector<vector<int>> a; // 图的邻接矩阵
    vector<int> x; // 当前解
    int n; // 图的顶点数
    int m; // 颜色数
    long long sum; // 当前已找到的可m着色方案数
public:
    void Backtrack(int i);
    Color() : sum(0) {}
    Color(vector<vector<int>> &&aa, int mm) : a(aa), m(mm), n(aa.size()), sum(0) { x.resize(n); }
    long long GetSum() { return sum; }
};

bool Color::Ok(int k) {
    for (int i = 0; i < k; i++) {
        if (a[k][i] && x[i] == x[k]) {
            return false;
        }
    }
    return true;
}

void Color::Backtrack(int i) {
    if (i > n) {
        sum++;
        for (int j = 0; j < n; j++) {
            cout << x[j] << " ";
        }
        cout << endl;
    } else {
        for (int j = 1; j <= m; j++) {
            x[i] = j;
            if (Ok(i)) {
                Backtrack(i + 1);
            }
            //x[i] = 0;
        }
    }
}

int mColoring(vector<vector<int>> &&a, int m) {
    Color X(std::move(a), m);
    X.Backtrack(0);
    return X.GetSum();
}

n皇后问题

在 $n \times n$ 的棋盘上放置 $n$ 个皇后，使得任意两个皇后都不在同一行、同一列或同一斜线上。求所有可能的放置方案。

确定问题状态：问题的状态即棋盘的布局状态。
构造状态空间树：状态空间树的根为空棋盘，每个布局的下一步可能布局是该布局结点的子结点。

由于可以预知，在每行中有且只有一个皇后，因此可采用逐行布局的方式，即每个布局有n个子结点。

n皇后问题的算法设计

将棋盘从左至右，从上到下编号为 $1,\dots,n$ ，皇后编号为 $1,\dots,n$ 。
设解为 $(x_1, \dots, x_n)$ ， $x_i$ 为皇后 $i$ 的列号，且 $x_i$ 位于第 $i$ 行。
解空间： $E=\{(x_1,..., x_n) \mid x_i \in S_i, i=1,...,n\}$ ， $S_i=\{1, ..., n\}$ ， $1 \leq i \leq n$
解空间为排列树。
其约束集合 $D$ 为

$x_i \neq x_j$
$x_i - i \neq x_j - j$
$x_i + i \neq x_j + j$

class Queen {
private:
    vector<int> x; // 当前解
    int n; // 皇后个数
    long long sum; // 当前已找到的可行方案数
    bool place(int k);
public:
    void Backtrack(int t);
    Queen() : sum(0) {}
    Queen(int nn) : n(nn), sum(0) { x.resize(n + 1); }
    long long GetSum() { return sum; }
};

bool Queen::place(int k) {
    for (int j = 1; j < k; j++) {
        if (abs(k - j) == abs(x[j] - x[k]) || x[j] == x[k]) {
            return false;
        }
    }
    return true;
}

void Queen::Backtrack(int t) {
    if (t > n) {
        sum++;
        for (int i = 1; i <= n; i++) {
            cout << x[i] << " ";
        }
        cout << endl;
    } else {
        for (int i = 1; i <= n; i++) {
            x[t] = i;
            if (place(t)) {
                Backtrack(t + 1);
            }
        }
    }
}

int nQueen(int n) {
    Queen X(n);
    X.Backtrack(1);
    return X.GetSum();
}

分支限界法

分支限界法的基本思想

分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。
问题的解空间树是表示问题解空间的一棵有序树，常见的有子集树和排列树。在搜索问题的解空间树时，分支限界法与回溯法的主要区别在于它们对当前扩展结点所采用的扩展方式不同。在分支限界法中，每个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。
从活结点表中选择下一扩展结点的不同方式导致不同的分支限界法。最常见的有以下两
种方式。

队列式分支限界法

队列式分支限界法将活结点表组织成一个队列，并按队列的先进先出原则选取下一个结点为当前扩展结点。

叶子结点不能加入队列，因为叶子结点没有儿子结点。叶子结点是问题的一个解，应该直接输出。

优先队列式分支限界法

优先队列式的分支限界法将活结点表组织成一个优先队列，并按优先队列中规定的结点优先级选取优先级最高的下一个结点成为当前扩展结点。
优先队列中规定的结点优先级常用一个与该结点相关的数值p来表示。结点优先级的高低与p值的大小相关。
最大优先队列规定p值较大的结点优先级较高。在算法实现时，通常用最大堆来实现最大优先队列，用最大堆的 Deletemax 运算抽取堆中下一个结点成当前扩展结点，体现最大效益优先的原则。
类似地，最小优先队列规定p值较小的结点优先级较高。在算法实现时，通常用最小堆来实现最小优先队列，用最小堆的 Deletemin 运算抽取堆中下一个结点成为当前扩展结点，体现最小费用优先的原则。

活结点表

每个活结点只有一次机会成为扩展结点，一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。

算法导论笔记

算法概述

算法的定义

算法的性质

程序与算法的区别

问题求解

算法复杂度

复杂性的计量

时间复杂度

复杂性的渐进性态

渐进性态

渐进性态的阶

大OOO表示法（上限）

大Ω\OmegaΩ表示法（下限）

大Θ\ThetaΘ表示法

NP完全性理论

P类问题

NP类问题

递归与分治策略

递归的概念

排列问题

整数划分

递归的优缺点

分治法

分治法所能解决的问题特征

分治法基本思想

分治法基本步骤

分治法求解过程

分治法的时间复杂性

二分法

找金块

棋盘覆盖

大整数的乘法

Strassen矩阵乘法

合并排序

快速排序

线性时间选择

最接近点对问题

一维最接近点对

二维最接近点对

动态规划

动态规划的基本思想

动态规划的实质

动态规划的特点

动态规划的基本步骤

动态规划基本要素

最优子结构性质

重叠子问题性质

矩阵连乘问题

分析最优解结构

建立递归关系

自底向上计算最优值

构造最优解

最长公共子序列

最长公共子序列的结构

子问题的递归结构

计算最优值

构建LCS

算法改进

最大子段和

凸多边形三角剖分

图像压缩

图像压缩的最优子结构

图像压缩的递归结构

电路布线

电路布线的最优子结构

递归计算最优值

构造最优解

流水线作业调度

流水线作业调度的最优子结构

流水线作业调度的递归计算最优值

流水线作业调度的Johnson法则

流水线作业调度的总时间

0-1背包问题

0-1背包问题的最优子结构

0-1背包问题的递归计算最优值

0-1背包问题的跳跃点解法

贪心算法

活动安排问题

证明活动安排问题的贪心选择性质

大 $O$ 表示法（上限）

大 $\Omega$ 表示法（下限）

大 $\Theta$ 表示法

证明每一步贪心选择→问题的整体最优解

上界函数-解决右子树剪枝问题

构造最优解-装载问题的回溯算法