1 算法分析

1.1 渐近分析的记号

image-20220528143943343 image-20220528143952643 image-20220528143959881

1.2 主定理

主定理方法应用于如下的递归形式：$T(n) = aT(n/b) + f (n) $，其中，$a\geq1, b \geq 1$，$f$ 是渐近正的。

image-20220528152727167 image-20220601094053688

2 分治与递归

2.1 阶乘函数

image-20220320161510908

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//阶乘函数
# include <iostream>
using namespace std;
int factorial(int n) 
{
    if (n == 0)
        return 1;
    else
        return n * factorial(n - 1);
}
int main()
{   
    int n;
    cin >> n;
    cout << factorial(n) << endl;
    return 0;
}

2.2 Fibonacci数列

image-20220320161403851

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// Fibonacci数列
# include<iostream>
using namespace std;
int fibonacci(int n){
    if (n <= 1)
        return 1;
    return fibonacci(n-1) + fibonacci(n-2);
}
int main(){
    int n;
    cin >> n;
    cout << fibonacci(n) << endl;
    return 0;
}

2.3 全排列问题

image-20220320161642543

思路：

  • 定义函数perm(int list[], int k, int m)表示获取list[k:m]的全排列。
  • 递归条件：
    • 当n=1时，全排列只有一种，即为它本身。
    • 当n>1时，可以依次将每一个数作为前缀，然后对后续n-1个数进行全排列。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
// 全排列
# include<iostream>
using namespace std;
void swap(int &a, int &b){
    int tmp = a;
    a = b;
    b = tmp;
}
//产生list[k:m]的全排列
int perm(int list[], int k, int m){
    if (k == m) { //只剩一个元素
        for(int i =0;i <=m;i++){
            cout << list[i];
        }
        cout << endl;
    }
    else {
        //还有多个元素，递归产生排列
        for (int i = k; i<=m; i++) { 
            //k到m的元素依次作为前缀,生成剩余数的全排列
            swap(list[k], list[i]);
            perm(list, k+1, m);
            swap(list[k], list[i]);
        }
    }
}
int main(){
    int a[] = {1,2,3};
    perm(a, 0, 2);
    return 0;
}

2.4 整数划分问题

image-20220320162315684

image-20220320162341988

（1）递归解法

思路：对整数n进行划分，将最大加数不大于m的划分个数记作 $q(n,m)$

对于$q(n,m)$：

  • 当n=1,m=1时，整数划分只有一种结果

  • 当n<m时，q(n,m)等价于q(n,n)

  • 当n=m时，共有1+q(n,m-1)中划分结果：

    • 整数划分中包含m，则只有一种划分结果，即{m}
    • 整数划分中不包含m，则意味着划分中的最大整数位m-1，即需递归解决q(n,m-1)

  • 当n>m时，共有q(n-m,m)+q(n,m-1)中划分结果

    • 整数划分中包含m，即划分为{m,{..}，这其中除了m外，其余部分可以看成对n-m继续进行划分，最大值可能为m,需递归解决q(n-m,m)
    • 整数划分中不包含m，即划分结果中最大为m-1，递归解决q(n,m-1)

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
//整数划分问题（递归解法） https://developer.aliyun.com/article/445250
//TODO: 动态规划解法
#include <iostream>
using namespace std;
int q(int n, int m){
    if (n == 1 || m == 1) {
        return 1;
    }
    if (n < m) {
        // 最大的划分不会超过n，所以等价于q(n, n)
        return q(n, n); 
    }
    if (n == m) {
        // (1)划分中包含m，则划分就为{m}，只有一个数
        // (2)划分中不包含m，则划分中的最大数只能为m-1，即递归划分为q(n,m-1)个数
        return 1 + q(n, m - 1);
    }
    if (n > m) {
        // (1) 划分中包含m，即{m, {...}}, 其中除了m外，其余的看成对n-m继续进行划分，最大值可能为m, 即为q(n, m)
        // (2) 划分中不包含m，即划分中的所有数都要小于m，即看成为q(n,m-1)
        return q(n - m, m) + q(n, m - 1);
    }
}

int main(int argc, char const *argv[])
{
    int n,m;
    cin >> n >> m;
    cout << q(n,m) << endl;
    return 0;
}

（2）动态规划解法

TODO

2.5 棋盘覆盖问题

image-20220320200745108

image-20220320200807568

思路：

  • 分治法将棋盘划分为四个区域，从而得到四个子问题进行解决。

  • 特殊方格必然位于四个区域中的其中一个，但是另外三个区域则没有特殊方格，导致了子问题不相同。因此，可以假设先用一个L型骨牌放在四个区域的交界处当作特殊方格，从而使每一个区域内都存在一个特殊方格，如下图所示：

    image-20220320201130769

  • 通过这样的分割和假设，棋盘分割问题就可以转化为四个1/4规模的子问题。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
//棋盘覆盖问题
#include <cstdio>
#include <vector>

int tile = 0;              // L型骨牌的编号
int Board[100][100] = {0}; //存放棋盘

void ChessBoard(int tr, int tc, int dr, int dc, int size)
{
    if (size == 1)
        return;
    int t = ++tile;   //表示L型骨牌的编号
    int s = size / 2; //划分区域

    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); //有特殊方格后则可以继续解决该子问题
    }
}
int main()
{

    int size = 8;
    int special_row = 3;
    int special_col = 4;

    ChessBoard(0, 0, special_row, special_col, size);

    for (int i = 0; i < size; i++)
    {
        for (int j = 0; j < size; j++)
        {
            printf("%2d ", Board[i][j]);
        }
        printf("\n");
    }
    return 0;
}

2.6 归并排序

递归的解法：

  • 先对nums[l:m]进行排序，再对nums[m+1:r]进行排序。
  • 将排好序的两部分合并，合并的时候先创建一个临时tmp，然后依次比较两部分的数值大小，将较小的放入tmp，然后移动指针；如果某一部分的元素已经全部放入，将另一部分剩余元素直接放入即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
/* 
P22
2.7 合并排序
*/
# include <cstdio>
# include <vector>
using namespace std;

void merge(vector<int> &nums, int l, int m, int r)
{

    vector<int> tmp(r - l + 1);  //一定要初始化
    // vector<int> tmp;          // segmentation fault

    int i = l, j = m + 1;
    int cnt = 0;
    while(i <= m && j <= r) {
        if (nums[i] <= nums[j]) {
            tmp[cnt++] = nums[i++];
        } else {
            tmp[cnt++] = nums[j++];
        }
    }
    // j已经全部放入，i还有剩余元素
    while(i <= m) {     
        tmp[cnt++] = nums[i++];
    }
    // i已经全部放入，i还有剩余元素
    while(j <= r) {
        tmp[cnt++] = nums[j++];
    }

    //将[l:r]放回原数组
    for (int i = 0; i < r - l + 1; i++) {
        nums[i + l] = tmp[i];
    }
}
void mergeSort(vector<int> &nums, int l, int r)
{
    if (l >= r)
        return;
    int m = (l + r) / 2;
    mergeSort(nums, l, m);      // 对nums中的l到m进行排序
    mergeSort(nums, m + 1, r);  // 对nums中的m+1到r进行排序
    merge(nums, l, m, r);          // [l:m]和[m+1:r]已经排好序，将他们进行合并
}

int main(){
    vector<int> a{2, 4, 6, 2, 3, 5, 8};
    mergeSort(a, 0, (int)a.size() - 1);
    for (auto i:a){
        printf("%d ", i);
    }
    return 0;
}

2.7 整数因子分解问题

image-20220323164805370

1
2
3
4
5
6
1: 1
2: 2
3: 3
4: 4 2*2
5: 5
6: 6 2*3 3*2

（1）解法一：递归

思路：

  • 当n=1时，只有一种分解方式。
  • 当n>1时，solve(n)可以对n的每一个因子再去求该分解子问题。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <iostream>
using namespace std;

int result = 0;

void solve(int n)
{
    if (n == 1)
    {
        result++;
    }
    else {
        for (int i = 2; i <= n; i++) {
            if (n % i == 0) {
                solve(n/i);
            }
        }
    }
}

int main()
{
    solve(12);
    cout << result << endl;
    return 0;
}

3 动态规划

3.1 矩阵连乘问题

image-20220407102052704

（1）最优子结构

将$A_i A_{i+1} \dots A_j$的矩阵连乘定义为$A[i:j]$，那么现假设在位置$k$ 加括号使$A[i:j]=A[i:k]A[k+1:j]$，那么总计算量就等于$A[i:k]$的计算量加上$A[k+1:j]$的计算量，再加上这矩阵相乘的计算量$p_{i-1}p_k p_j$。

并且，计算$A[i:j]$的最优次序所包含的计算矩阵子链$A[1:k]$和$A[k+1:j]$的次序也是最优的，即具有最优子结构性质。

反证：如果$k$不是最优的，即存在一个更好的划分位置$k’$使$A[1:k’]$或$A[k’+1:j]$的计算量更少，那么得到的$A[1:n]$计算量也会比最优次序的计算量更少，导致矛盾。

（2）建立递归关系

用$m[i][j]$存储$A[i][j]$的最优次序计算量，则原问题的最优值为$m[1][m]$。

  • 当$i=j$时，只有一个矩阵，因此$m[i][j]=0$
  • 当$i<j$时，假设在$k$断开，则$m[i][j]=m[i][k]+m[k+1][j]+p_{i-1} p_k p_j$，由于$k$的位置不确定，因此这里需要取$min$。

递归式如下：
$$
m[i][j]= \begin{cases}0 & i=j \ \min {i \leqslant k<j}\left{m[i][k]+m[k+1][j]+p{i-1} p_{k} p_{j}\right} & i<j\end{cases}
$$
除此之外，还可以顶一个$s[i][j]$用来存储最优断开位置$k$，在计算出最优值$m[i][j]$后，可递归地由$s[i][j]$构造出相应的最优解。

（3）构造最优解

s[i][j]记录了A[i:j]最佳断开的位置k，因此当求解A[1:n]的最优加括号方式，只需要递归得查找A[i:k]和A[k+1][j]得最优加括号方式，即A[1:s[1][n]]和A[s[1][n]+1:n]。

（4）算法复杂度为$O(n^3)$

image-20220524153317507

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
// 矩阵连乘
#include <iostream>
#include <vector>
using namespace std;

// p0p1  p2p3 p4p5  p6p7 p8p9
//  A1    A2   A3    A4   A5
// n表示矩阵个数
void MatrixChain(vector<int> &p, int n, vector<vector<int>> &m, vector<vector<int>> &s)
{
    for (int i = 0; i < n; i++)
    {
        m[i][i] = 0;
    }
    for (int r = 2; r <= n; r++)
    { // 矩阵链的个数,从2个矩阵开始
        for (int i = 1; i <= n - r + 1; i++)
        {
            int j = i + r - 1; //
            //遍历断开的位置k,找到最优次序(计算量最小)
            m[i][j] = m[i + 1][j] + p[i - 1] * p[i] * p[j]; //先假设在矩阵i后段断开
            s[i][j] = i;
            //从i+1出遍历断开位置k，找到最优次序
            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] = i;
                    s[i][j] = k;
                }
            }
        }
    }
}

//构造最优解
void Traceback(int i, int j, vector<vector<int>> &s)
{
    if (i == j)
        return;
    Traceback(i, s[i][j], s);
    Traceback(s[i][j] + 1, j, s);
    cout << "Multiply A " << i << ", " << s[i][j];
    cout << " and A" << s[i][j] + 1 << ", " << j << endl;
}

int main()
{

    vector<int> p{30, 35, 35, 15, 15, 5, 5, 10, 10, 20, 20, 25};
    vector<vector<int>> m(12, vector<int>(12, 0));
    vector<vector<int>> s(12, vector<int>(12, 0));

    MatrixChain(p, 6, m, s);
    Traceback(1, 6, s);
    return 0;
}

3.2 最长公共子序列

image-20220407140718590

（1）最优子结构

设序列$X_m={x_1,x_2,\dots,x_m}$和$Y_n={y_1,y_2,\dots,y_n}$的最长公共子序列为$Z_k={z_1,z_2,\dots,z_k}$，可以从后往前看：

  • 如果$x_m=y_n$，那么这个数一定在公共子序列中，即$z_k=x_m=y_n$，那么原问题的规模下降为求解$X_{m-1}$和$Y_{n-1}$的最长公共子序列$Z_{k-1}$
  • 如果$x_m \neq y_n$且$z_k \neq x_m$，那么$x_m$一定不在公共子序列中，因此原问题规模可以下降为求解$X_{m-1}$和$Y_n$的最长公共子序列$Z_k$
  • 如果$x_m \neq y_n$且$z_k \neq y_n$，那么$y_n$一定不在公共子序列中，因此原问题规模可以下降为求解$Y_{n-1}$和$X_m$的最长公共子序列$Z_k$

反证：

  • 如果$z_k \neq x_m$，那么也就说明$z_k$后面还有一个公共数，即${z_1,z_2,\dots,z_k,x_m}$，那么此时公共子序列的长度为$k+1$，与$Z_k$是$X$和$Y$的最长公共子序列矛盾，因此必有$z_k=x_m=y_n$。同样的，如果$X_{m-1}$和$Y_{n-1}$有长度大于$k-1$的公共子序列$W$，那么将$x_m=y_n$加在该序列末尾，会导致$X_m$和$Y_n$的最长公共子序列长度大于$k$，矛盾。因此，$Z_{k-1}$是$X_{m-1}$和$Y_{n-1}$的最长公共子序列。
  • 因为$z_k \neq x_m$，$Z_k$是$X_{m-1}$和$Y$的公共子序列，若$X_{m-1}$和$Y$有长度大于$k$的公共子序列$W$，则$W$应该也是$X_m$和$Y_n$的公共子序列，与$Z_k$是$X_m$和$Y_n$最长公共子序列矛盾。

因此，最长公共子序列问题包含了两个序列前缀的最长公共子序列的子问题，且具有最优子结构的性质。

（2）构造递归方程

  • 如果$x_m=y_n$，那么这个数一定在公共子序列中，此时只需要找到$X_{m-1}$和$Y_{m-1}$的最长公共子序列，再在其末尾加上$x_m(x_m=y_n)$即可。
  • 如果$x_m \neq y_n$，那么就需要在$X_{m-1}$和$Y_n$以及$X_m$和$Y_{n-1}$两个最长公共子序列子问题中，找出更大的那个序列。

递归方程如下，$c[i][j]$表示$X_i$与$Y_j$的最长公共子序列长度：
$$
c[i][j]= \begin{cases}
0 & i>0 ; j=0 \
c[i-1][j-1]+1 & i, j>0 ; x_{i}=y_{i} \
\max {c[i][j-1], c[i-1][j]} & i, j>0 ; x_{i} \neq y_{i}\end{cases}
$$
（3）最优解

如果除了LCS的长度，还想获取具体的LCS序列，则还需要一个$b[i][j]$用来记录当前采取了哪种子问题，从而在构造LCS的时候，可以递归地进行打印。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
//  最长公共子序列
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

// 计算最优值
void LCSLength(int m, int n, string x, string y, vector<vector<int>> &c, vector<vector<int>> &b)
{
    for (int i = 0; i <= m; i++)
    {
        for (int j = 0; j <= n; j++)
        {
            // 如果x和y中有一个序列长度为0, 则LCS长度为0
            if (i == 0 || j == 0)
            {
                c[i][j] = 0;
            }
            else if (x[i - 1] == y[j - 1])
            {
                c[i][j] = c[i - 1][j - 1] + 1;
                b[i][j] = 1;
            }
            else if (c[i - 1][j] > c[i][j - 1])
            {
                c[i][j] = c[i - 1][j];
                b[i][j] = 2;
            }
            else
            {
                c[i][j] = c[i][j - 1];
                b[i][j] = 3;
            }
        }
    }
}

// 构造最优解
void LCS(int i, int j, string x, vector<vector<int>> &b)
{
    if (i == 0 || j == 0)
        return;
    if (b[i][j] == 1)
    {
        LCS(i - 1, j - 1, x, b);
        cout << x[i - 1];
    }
    else if (b[i][j] == 2)
    {
        LCS(i - 1, j, x, b);
    }
    else
    {
        LCS(i, j - 1, x, b);
    }
}

int main()
{
    // string x = "programming";
    // string y = "contest";
    string x = "abcfbc";
    string y = "abfcab";
    int m = x.size();
    int n = y.size();

    vector<vector<int>> c(m + 1, vector<int>(n + 1, -1));
    vector<vector<int>> b(m + 1, vector<int>(n + 1, -1));

    LCSLength(m, n, x, y, c, b);
    cout << c[m][n] << endl;
    LCS(m, n, x, b);
    return 0;
}

3.3 最大字段和

image-20220410104055295

（1）分治法：

  • 将原问题$a[1:n]$的最大子段和分解为$a[1:n/2]$和$a[n/2+1,n]$的两个子问题，分别求这两个子问题的最大子段和。

  • 在这两个子问题进行合并的时候，会存在以下三种情况：

    • $a[1:n]$的最大子段和与子问题$a[1:n/2]$的最大子段和相同。
    • $a[1:n]$的最大子段和与子问题$a[n/2+1:n]$的最大子段和相同。
    • $a[1:n]$的最大子段和$\sum_{k=i}^j{a_k}$的开始位置$i<n/2$，结束位置$j>n/2+1$。

  • 对于前两种情况，直接递归求解即可。对于第三种情况，$a[n/2]$和$a[n/2+1]$肯定在最优子段中，那么只需从位置$n/2$分别向前、向后找到最大的子段，也就是
    $$
    最大子段和=\max_{1 \leq i \leq n/2} \sum_{k=i}^{n/2}a[k] + \max_{n/2+1 \leq i \leq n} \sum_{k=n/2+1}^{j}a[k]
    $$

  • 复杂度分析：子问题规模为$n/2$,合并需要$O(n)$，递归式如下，解得$T(n)=O(n\log{n})$
    $$
    T(n) =
    \begin{cases}
    O(1) & n \leq c \
    2T(n/2) + O(n) & n \gt c

    \end{cases}
    $$

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
// 最大子段和
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// 分治法
int MaxSubSum(vector<int> &a, int left, int right)
{
    int sum = 0;
    // 当所有整数为负整数时定义最大子段和为0
    if (left == right)
    {
        sum = a[left] > 0 ? a[left] : 0;
    }
    else
    {
        int mid = (left + right) / 2;
        int leftSubSum = MaxSubSum(a, left, mid);
        int rightSubSum = MaxSubSum(a, mid + 1, right);

        //在左边找到最大的子段
        int s1 = 0;
        int leftSum = 0;
        for (int i = mid; i >= left; i--)
        {
            leftSum += a[i];
        }
        if (leftSum > s1)
        {
            s1 = leftSum;
        }
        //在左边找到最大的子段
        int s2 = 0;
        int rightSum = 0;
        for (int i = mid + 1; i <= right; i++)
        {
            rightSum += a[i];
        }
        if (rightSum > s2)
        {
            s1 = rightSum;
        }

        sum = leftSum + rightSum;
        if (sum < leftSum)
        {
            sum = leftSum;
        }
        if (sum < rightSum)
        {
            sum = rightSum;
        }
    }
    return sum;
}

int maxSum(int n, vector<int> &a)
{
    // a[1:n]的最大子段和
    return MaxSubSum(a, 1, n);
}


int main()
{
    int res;
    vector<int> a{-2, 11, -4, 13, -5, -2};

    res = maxSum(6, a);
    cout << "res:" << res << endl;
    return 0;
}

（2）动态规划

设$b[i-1]$表示$a[1:i-1]$的最大子段和，那么对于第$i$个元素$a[i]$来说，它要么合并到$a[1:i-1]$的最大子段中，要么重新成为一个新的子段，取决于$b[i-1]+a[i]$和$a[i]$的大小。

因此，动态规划的递归式如下：
$$
b[i] = \max { b[i-1] + a[i], a[i]},\space 1 \leq i \leq n
$$
该方法只需要遍历一次序列，复杂度为$O(n)$

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
// 最大子段和
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int maxSum(int n, vector<int> &a)
{
    int prev = 0, maxSum = a[0];
    for (const auto x:a)
    {
        prev = max(prev + x, x);
        maxSum = max(prev, maxSum);
    }
    return maxSum;
}

int main()
{
    int res;
    vector<int> a{-2, 11, -4, 13, -5, -2};

    res = maxSum(6, a);
    cout << "res:" << res << endl;
    return 0;
}

动态规划的遍历方式通常是以序列的结束节点为基准，如下：

image-20220410111715319

3.4 凸多边形最优三角剖分

image-20220410135646280

image-20220410135702182

思路：

  • 本质上与矩阵连乘问题类似，定义$t[i][j](1 \leq i \lt j \leq n)$ 为凸多边形 ${v_{i-1},v_i,\dots,v_j }$ 的最优三角剖分对应的权函数值。因此，原问题计算凸$n+1$边形的最优权值为$t[1][n] ({v_0,v_1,\dots,v_n})$。

  • 若只有两条边，定义权值为零，即$t[i][i]=0(i=1,2,\dots,n)$。

  • 当至少有三个顶点时($j-i\ge 1$)时，以$v_{i-1}v_j$的弦底边，某一个点$v_k$为顶点，将凸多边形划分成了${v_{i-1},v_{i}\dots,v_k}$和${v_{k},v_{k+1},\dots,v_j}$两个凸多边形，以及一个三角形${v_{i-1},v_k,v_j}$，这两个划分出来的凸多边形构成了子问题$t[i][k]$和$t[k+1][j]$，且具有最优子结构性质。

  • 因此，原问题$t[i][j]$就等于了$t[i][k]+t[k+1][j]$再加上三角形的权值$w(v_{i-1} v_k v_j)$。而现在不确定最优划分的$v_k$的位置，所以$t[i][j]$的递归式定义如下，时间复杂度为$O(n^3)$：
    $$
    t[i][j]= \begin{cases}0 & i=j \ \min {i \leqslant k \leqslant j}\left{t[i][k]+t[k+1][j]+w\left(v{i-1} v_{k} v_{j}\right)\right} & i<j\end{cases}
    $$

  • 若想构造最优三角剖分，还需要定一个数组$s[i][j]$用于记录$v_k$的顶点位置，时间复杂度为$O(n)$

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void MinWeightTriangulation(int n, vector<vector<int>> &t, vector<vector<int>> &s)
{
    for (int i = 1;i<=n;i++) { //只有两个顶点
        t[i][i] = 0;
    }
    for (int r = 2; r <= n; r++) {  /
        for (int i = 1; i <= n - r + 1; i++)
        {
            int j = i + r - 1; 
            t[i][j] = t[i + 1][j] + w(i - 1, i, j);
            for (int k = i + 1; k < i + r - 1; k++) {
                int u = t[i][k] + t[k + 1][j] + w(i - 1, k, j);
                if (u < t[i][j]) {
                    t[i][j] = u;
                    s[i][j] = k;
                }
            }
        }
    }
}

3.5 多边形游戏

image-20220412203445335

image-20220412203508963

书上讲的挺清楚，直接放上来。

image-20220412204800514

image-20220412204813897

image-20220412204825130

3.6 图像压缩

在计算机中，常用像素点的灰度值序列${p_1,p_2,\dots, p_n}$表示图像。其中整数$p_i(1 \leq i \leq n)$，表示像素点$i$的灰度值($0 \sim 255$)，因此最多需要8位表示一个像素。

图像压缩就是将像素点序列${p_1,p_2,\dots, p_n}$分割成$m$个连续段$S_1,S_2,\dots,S_m$。

  • 其中$S_i$中有$l[i]$个像素，且该段中每个像素都只用$b[i]$位表示，也就是“要表示该段中最大的数字需要的位数”，这样每一个像素段就可以用$l[i]*b[i]$位来存储。

  • 除此之外，还需要用一定的存储空间来表示每一段的$b[i]$和$l[i]$的值，$b[i]$最大为8，也就是需要3位来表示，如果限制$l[i]$的最大值位256，那么就需要8位来表示。

  • 因此，每一段子序列$S_i$所需要的存储空间就为$l[i]*b[i]+11$，总共需要的存储空间为$\sum_{i=1}^{m}l[i]b[i]+11m$

现在图像压缩问题，就是确定像素序列${p_1,p_2,\dots, p_n}$的最优分段，使得依此分段所需的存储空间最小。其中，$0 \leq p_i \leq 256, \space 1 \leq i \leq n$，每个分段长度不超过256位。

（1）最优子结构(?)

假设$l[i]$和$b[i]$($1 \leq i \leq m$)是${p_1,p_2,\dots,p_n}$的一个最优分段。显然$l[1]、b[1]$是${p_1,\dots,p_{l[1]}}$的一个最优分段，且$l[i]$和$b[i]$($2 \leq i \leq m$ )是${p_{l[1]+1},\dots,p_n }$的一个最优分段，即满足最优子结构性质。

（2）递归计算最优值

设$s[i]$($1 \leq i \leq n$)是像素序列${p_1,p_2,\dots,p_i}$的最优分段所需要的存储位数，以下面这个例子说明：

image-20220413115012969

  • $s[0]$：当没有像素的时候肯定为0，也就是$s[0]=0$
  • $s[1]$：当像素序列长度为1时，直接用该段所需的最大存储位(上例位3)，再加上用于存储b和l的11
  • $s[2]$：当像素序列长度大于2时，就考虑在哪里进行分段，并取下面这些情况的最小值：
    • 不分段，即将这2个像素看成一段，那么还是用该段所需的最大存储位数(3)乘上该段的像素数量(2)，再加上11。
    • 从$p_1$后面分段，前面一段的最优存储空间直接用$s[1]$表示；第二段用该段所需的最小存储位数(3)乘上该段的像素数量(1)，再加上11。
  • $s[3]$：当计算序列长度为3的最优存储空间，依然是寻找在哪里进行分段，此时有三种情况，取其中的最小值：
    • 不分段，将前3个像素看成一段，就是直接用该段所需的最大存储位数(3)乘上该段的像素数量(3)，再加上11。
    • 从$p_1$后面分段，前面一段的最优存储空间直接用$s[1]$表示；第二段用该段所需的最大存储位数(3)乘上该段的像素数量(2)，再加上11。
    • 从$p_2$后面分段，前面一段的最优存储空间直接用$s[2]$表示；第二段用该段所需的最大存储位数(3)乘上该段的像素数量(1)，再加上11。
  • 以此类推，知道计算出$s[n]$即为$p_1,\dots,p_n$的最优分段所需的存储空间。

因此，递归式为：
$$
\begin{gathered}
s[i]=\min _{1 \leqslant k \leqslant \min {i, 256}}{s[i-k]+k * b \max (i-k+1, i)}+11 \
\operatorname{bmax}(i, j)=\left[\log \left(\max {i \leqslant k \leqslant j}\left{p{k}\right}+1\right)\right]
\end{gathered}
$$
上式中$bmax(i,j)$就是为了找到${p_i,\dots,p_j}$段中所需要的存储位数。

（3）代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
void Compress(int n, int p[], int s[], int l[], int b[])
{
    int Lmax = 256, header = 11;
    s[0] = 0;
    for (int i = 1; i <= n; i++)
    {
        b[i] = binaryLen(p[i]);
        int bmax = b[i];
        // 在p_{i-1}处分段，前一段直接为s[i-1],后一段即为p_i的二进制表示位数bmax
        s[i] = s[i - 1] + bmax;
        l[i] = 1;
        // 因此向前遍历分段的位置
        for (int j = 2; j <= i && j <= Lmax; j++)
        {
            if (bmax < b[i - j + 1])
            {
                bmax = b[i - j + 1];
            }
            //若在p_j处分段，前一段存储空间为s[i-j]，后一段为其中的最大表示位数bmax，乘上后一段的像素数量j
            if (s[i] > s[i - j] + j * bmax)
            {
                s[i] = s[i - j] + j * bmax;
                l[i] = j;
            }
        }
        s[i] += header;
    }
}

// 用二进制表示i所需的位数
int binaryLen(int i)
{
    int k = 1;
    i = i / 2;
    while (i > 0)
    {
        k++;
        i = i / 2;
    }
    return k;
}

3.7 流水作业调度

image-20220525105706342

完成集合 $S$ 中作业所需的最短时间为 $T(S,t)$，表示机器 $M_1$ 开始加工 $S$ 中作业时，机器 $M_2$ 还需要等待 $t$ 时间后才可用，因此原问题的最优值为 $T(N,0)$。

（1）最优子结构

设原问题 $N = {1,2,\dots,n}$ 的最优调度为 $\pi$ （即$n$个作业的一个排列），所需加工时间为 $a_{\pi(1)}+T(S,b_{\pi(1)})$，其中子问题 $S=N-{\pi(1)}$。若 $S$ 存在更优的调度 $T’(S,b_{\pi(1)})$，即 $T’(S,b_{\pi(1)})< T(S,b_{\pi(1)})$，那么可以得到$a_{\pi(1)}+T’(S,b_{\pi(1)}) < a_{\pi(1)}+T(S,b_{\pi(1)})$，与 $\pi$ 是原问题的最优解矛盾，所以该问题满足最优子结构形式。

（2）构造递归方程

当$T(S,t)$加工第 $i$ 个作业时，$M_1$ 上需要需要时间 $a_i$， $M_2$ 开始加工第 $i$ 个作业前，需要等待 $\max {t,a_i}-a_i=\max {t-a_i, 0}$ 个时间，然后再需要$b_i$ 时间完成作业 $i$ 的加工，因此递归方程如下：
$$
T(S,t) = \min_{i \in S} {a_i+T(S-{i},b_i + \max{t-a_i,0})}
$$
（3）基于 Johnson 法则的流水调度算法

流水调度问题一定存在满足 Johnson 法则的最优调度，算法如下：

  • 令 $N_1={i|a_i < b_i}$，$N_2 = {i| a_i \geq b_i}$

  • 将 $N_1$ 中的作业依 $a_i$ 非减序排列，将 $N_2$ 中的作业依 $b_i$ 非增序排列。

    • $M_2$ 上任务等待的时间越少越好 => 在 $M_1$ 上加工时间短的排前面，在 $M_2$加工时间长的排在前面。

  • $N_1$中作业接 $N_2$ 中作业构成满足 Johnson 法则的最优调度

  • 算法复杂度为 $O(nlogn)$

image-20220524205234433 image-20220524205909299

3.8 0-1背包问题

image-20220525105722224

（1）最优子结构

设 $(y_1,y_2,\dots,y_n)$ 是原问题 $\max \sum_{i=1}^{n}v_i x_i, \sum_{i=1}^{n}w_ix_i \leq c$的最优解，则 $(y_2,\dots,y_n)$其子问题为 $\max \sum_{i=2}^{n}v_i x_i, \sum_{i=2}^{n}w_ix_i \leq c-w_1y_1$。否则，若子问题存在一个更优的解 $(z_2,\dots,z_n)$，即 $\sum_{i=2}^{n}v_i z_i \gt \sum_{i=2}^{n}v_i y_i$，那么可以得到 $v_1 y_1 + \sum_{i=2}^{n}v_i z_i \gt v_1 y_1 + \sum_{i=2}^{n}v_i y_i$，与 $(y_1,y_2,\dots,y_n)$ 是原问题的最优解矛盾，所以该问题满足最优子结构性质。

（2）构造递归方程

该问题的最优值为 $m(i,j)$ 表示背包容量为 $j$，可选择物品为 $i,i+1,\dots,n$ 时的0-1背包问题最优值，其递归式如下：
$$
\begin{gathered}
m(i, j)= \begin{cases}\max \left{m(i+1, j), m\left(i+1, j-w_{i}\right)+v_{i}\right} & j \geqslant w_{i} \
m(i+1, j) & 0 \leqslant j<w_{i}\end{cases} \
m(n, j)= \begin{cases}v_{n} & j \geqslant w_{n} \
0 & 0 \leqslant j<w_{n}\end{cases}
\end{gathered}
$$
（3）计算复杂性分析

该递归式需要 $O(nc)$ 的计算时间（算法相当于填一个二维表，行列分别是物品数量和背包最大容量）

（4）算法的改进

image-20220524220108676

改进后的算法复杂性为 $O(2^n)$

4 贪心算法

证明贪心选择策略

4.1 活动安排问题

image-20220418134358292

（1）贪心选择策略

每次将结束时间最早的活动优先安排，即留下尽可能多的时间给其他活动。

具体做法为，按活动的结束时间非减序排列，然后在安排完第一个活动后，以此判断后续活动是否与前一个安排的活动结束时间相容，相容则安排，不相容则不安排。

证明：设原问题 $E={1,2,\dots,n}$ 为所给活动集合，其中活动按结束时间非减序排列，即活动1具有最早完成时间。设该问题的的最优解为 $A$，且 $A$ 中的活动按结束时间 $f_i$ 非减序排列，$A$ 中第一个活动是活动 $k$。

  • 若 $k=1$，则 $A$ 为一个以贪心选择开始的最优解。
  • 若 $k \gt 1$，则设 $B=A - {k} \cup {1} $，（即用第1个活动替换第k个活动）因为 $f_1 \leq f_k$ 且 $A$ 中的活动是相容的，所以 $B$ 中的活动也是相容的。又因为 $|B|=|A|$，且 $A$ 是最优的，所以 $B$ 也是最优的，也就是说 $B$ 是以贪心选择活动 1 开始的最优活安排。
  • 综上，从存在以该贪心选择开始的最优活动安排方案。

（2）最优子结构

设子问题 $E’= {i \in E: s_i \geq f_1}$，若 $A$ 是原问题 $E$ 的最优解， 则 $A’=A-{1}$ 是子问题 $E’$ 的最优解。若$E’$ 存在更优的一个解 $A’’$，即 $A’’ < A’$，那么有 $A’’ \cap {1}<A’ \cap {1}=A$，与 $A$ 是原问题的最优解矛盾，所以该问题满足最优子结构性质。

（3）复杂度分析

按结束时间排序活动需要$O(n logn)$，按贪心算法安排活动需要$O(n)$，总共需要 $O(n long)$

image-20220620165341653

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
//假设已经按结束时间非减序
template <class Type>
//用集合A[i]=true表示安排的活动
void GreedySelector(int n, Type s[], Type f[], bool A[])
{
    // 降低一个活动加入集合A
    A[1] = true;
    int j = 1;
    for (int i = 2; i <= n; i++)
    {
        if (s[i] > f[j]) //如果第i个活动与上一个安排的活动相容
        {
            A[i] = true;
            j = i;
        }
        else
        {
            A[i] = false;
        }
    }
}

4.2 背包问题

image-20220418141319971

  • 与0-1背包问题的区别是，背包问题可以选择物体的一部分装入背包，因此可以使用贪心算法。

  • 贪心策略是每次优先将单位重量价值高的物品装入背包内。

  • 0-1背包由于每个物品只能选择装入或者不装入，如果使用贪心策略可能会导致背包容量的浪费，从而总价值达不到最优。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
// 背包问题
// 贪心策略: 优先将单位价值高的物品装入背包内

// 按照单位价值(v/w)对物品进行排序
void Sort(int n, float v[], float w[]);

void Knapsack(int n, float M, float v[], float w[], float x[])
{
    
    Sort(n, v, w); //按单位价值排序
    int i;
    // 初始化背包
    for (i = 1; i <= n; i++)
    {
        x[i] = 0;
    }
    float c = M;    //背包容量
    for (i = 1; i <= n; i++)
    {
        //如果当前的重量已大于背包容量
        if (w[i] > c)
            break;
        x[i] = 1;   // 在有容量的情况下尽可能将单位价值高的全装入
        c -= w[i];  //  更新背包剩余容量
    }
    // 当还有剩余物品，但背包容量不足以放下完整的物品, 放入一部分
    if (i <= n)
        x[i] = c / w[i];
}

4.3 最优装载

image-20220418143231291

（1）贪心选择策略

重量最轻的优先进行装载。

证明：设集装箱按照其重量非减序排列， $(x_1,x_2,\dots,x_n)$ 是原问题的一个最优解，设 $k= \min_{1 \leq i \leq n} {i|x_i=1}$，（第一个装入的集装箱为k），如果原问题有解，则 $1\leq k \leq n$。

  • 当 $k=1$ 时，$(x_1,x_2,\dots,x_n)$ 是满足贪心选择性质的一个最优解。
  • 当 $k \gt 1$ 时，取另一个解$(y_1,y_2,\dots,y_n)$ ，其中 $y_1=1,y_k=0,y_i=x_i,1 \lt i \leq n,i \neq k$，（也就是用第1个箱子替换掉原来装入的第k个箱子），又因为 $w_1 \leq w_k$，所以有 $\sum_{i=1}^{n}w_iy_i=\sum_{i=1}^{n}w_ix_i-w_k+w_1 \leq \sum_{i=1}^{n}w_ix_i \leq c$，即 $(y_1,y_2,\dots,y_n)$ 是装载问题的可行解，且 $\sum_{i=1}^{n}y_i=\sum_{i=1}^{n}x_i$，即$(y_1,y_2,\dots,y_n)$ 是满足贪心选择性质的最优解。
  • 所以，装载问题具有贪心选择性质。

（2）最优子结构性质

设 $A={x_1,x_2,\dots,x_n}$ 是原问题 $n$ 个集装箱 $E$ 的最优解，则 $A’=(x_2,x_3,\dots,x_n)$ 是子问题 $x_1=1$，轮船载重量$c-w_1$ 的子问题的最优解。若存在子问题更优的一个解 $A’’$，使得 $\sum_{x \in A’’} x_i \lt \sum_{x \in A’} x_i$，则可以得到 $x_1 + \sum_{x \in A’’} x_i \lt x_1 + \sum_{x \in A’} x_i = \sum_{x \in A} x_i$，与 $A$ 是原问题的最优解矛盾。因此，装载问题具有最优子结构性质。

（3）算法复杂度

重要复杂度来自于对集装箱重量的排序，即 $O(n \log{n})$。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// 对物品按照重量非减序排序
void Sort(float w[], int t[], int n);

void Loading(int x[], float w[], float c, int n)
{
    int *t = new int[n + 1];
    // 用t存放排好序后的物品编号
    Sort(w, t, n);
    for (int i = 1; i <= n; i++)
    {
        x[i] = 0;
    }
    for (int i = 1; i <= n && w[t[i]] <= c; i++)
    {
        x[t[i]] = 1;
        c -= w[t[i]];
    }
}

4.4 哈夫曼编码

贪心选择性质：每次选择频率最小的两棵子树进行合并，从而产生一棵新的子树，其频率为合并的两棵子树频率之和。n 个字符的哈夫曼算法复杂度为 $O(n \log{n})$。

image-20220620165512635

image-20220620165519629

哈夫曼编码的实例，频率小的字符深度大：

image-20220620165537701 image-20220620165545647

4.5 单源最短路径

image-20220525175135119

最优子结构性质：一个最短路径的子路径也是最短路径

算法基本思想——贪心：

  • 维护一个顶点集合 $S$，它们从原点 $s$ 的最短路径已知
  • 每一步添加 𝑣 ∈ 𝑉 − 𝑆 中具有最小距离的顶点到 S 中
  • 更新剩余顶点 v 的距离估计

Dijkstra算法（边权重非负，如果权重可能为负则采用Bellman-Ford算法）：

  • 初始时，S中仅含有源
  • 设 v 是 G 的某一个顶点，把从源到 v 且中间只经过 S 中顶点的路 称为从源到 v 的特殊路径，并用数组 dist 记录当前每个顶点所对 应的最短特殊路径长度
  • 每次从 V-S 中取出具有最短特殊路长度的顶点 v，将 v 添加到 S 中 ，同时对数组 dist 作必要的修改
  • 一旦 S 包含了所有 V 中顶点，dist 就记录了从源到所有其它顶点 之间的最短路径长度
  • 对于具有 $n$ 个顶点和 $e$ 条边的带权有向图，主循环需要 $O(n)$，循环执行 n-1次，所以复杂度为 $O(n^2)$。
image-20220620165649508 image-20220620165654992

Dijkstra算法的贪心选择策略是从 V - S 中选择具有最短特殊路径的顶点 u，从而确定从源到 u 的最短路径长度 dist[u]。

image-20220620165706534

image-20220620165716917

4.6 最小生成树

image-20220620165734836

（1）Prim 算法（选边）

设 $G=(V,E)$ 是连通带权图，$V={1,2,\dots,n}$。构造 $G$ 的最小生成树的 Prim算法基本思想是： 首先设置 $S={1}$，然后只要 $S$ 是 $V$ 的真子集，就做如下贪心选择：选取满足条件 $i \in S$，$j \in V-S$，且 $c[i][j]$ 最小的边，并将顶点 $j$ 添加到 $S$ 中。这个过程一直进行直到 $S=V$ 时为止，选取到的所有边恰好构成 $G$ 的一颗最小生成树。

贪心选择性质证明：上述算法中的边集合 T 始终包含 G 的某棵最小生成树中的边 (循环不变式)。因此，在算法结束时，T 中的所有边构成 G 的 一棵最小生成树

Prim 算法的时间复杂度为 $O(n^2)$。

image-20220620165744181

（2）Kruskal 算法

Kruskal算法构造 G 的最小生成树的基本思想：

  • 首先将 G 的 n 个顶点看成 n 个孤立的连通分支，将所有的边按权从小到大排序
  • 从第一条边开始，依边权递增的顺序查看每一条边，并按下述方法连接 2 个不同的连通分支：
    • 当查看到第 $k$ 条边 $(v,w)$ 时，如果端点 $v$ 和 $w$ 分别是当前 2 个不同的连通分支 $T_1$ 和 $T_2$ 中的顶点时，就用边 $(v,w)$ 将 $T_1$ 和 $T_2$ 连接成一个连通分支，然后继续查看第 $k+1$ 条边
    • 如果端点 $v$ 和 $w$ 在当前的同一个连通分支中，就直接再查看第 $k+1$ 条边
  • 这个过程一直进行到只剩下一个连通分支时为止
  • 当图的顶点数为 $n$，边数为 $e$ 时，Kruskal算法所需的计算时间是 $O(e \log{e})$
image-20220525204151155

4.7 多机调度问题

image-20220525210600671

这个问题是 NP完全问题，到目前为止还没有有效的解法， 对于这一类问题，用贪心选择策略有时可以设计出较好的近似算法。

贪心策略：最长处理时间作业优先。

  • 当 $n \leq m$ 时，只要将机器 $i$ 的 $[0, t_i]$ 时间区间分配给作业 $i$ 即可，算法只需要 $O(1)$ 时间
  • 当 $n \gt m$ 时，首先将 $n$ 个作业依其所需的处理时间从大到小排序；然后依此顺序将作业分配给空闲的机器处理。
  • 算法所需的时间复杂度为 $O(n \log{n})$
image-20220525211248692

4.7 会场安排问题

image-20220419142222514

image-20220419142240458

（1）贪心策略：

在满足与前一个活动相容的情况下，优先选择开始时间早的活动。

（2）最优子结构

设原问题为$E$的最优解为$A$，现在假设活动1为会场1中安排的第一个活动。那么，可以得到与活动1相容的子问题$E’=E-{1}$，现在需要证明$A’=A-{1}$是$E’$的最优解。

反证：假设存在子问题$E’=E-{1}$的一个最优解为$A’’$，那么有$|A’’|<|A’|$，即$|A’’ \cup {1}|<|A’ \cup {1}|=|A|$，与$A$是原问题$E$的最优解矛盾。

（3） 贪心选择性质

现在假设最优解$E$，按照活动的开始时间非减序排列${s_1,s_2,\dots,s_n}$，对应的结束时间为${f_1,f_2,\dots,f_n}$。

设在满足会场1相容条件(即开始时间大于会场1前一个活动结束时间)的前提下，第一个安排到会场1中的活动为$a_1$，而开始时间最早的活动为$a_k$。

  • 若 $k=1$，即为满足贪心选择性质的最优解。
  • 若$k \neq 1$，因为$s_k<s_1$，所以它们一定不会安排在同一个会场。假设活动$a_k$安排在第$m$个会场，会场$m$前一个活动为$a_x$，即有$s_k \geq f_x $。现在将$a_1$与$a_k$的会场进行互换得到解$E’$，因为$a_1$与$a_k$均满足会场1的相同条件，且$s_1 \gt s_k \geq f_x$，即$a_1$也满足会场$m$的相容条件，所以$E’$为该问题的一个可行解。又因为$|E’|=|E|$，所以$E’$是满足贪心选择性质的最优解。

（4）代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
/*
 * @Author: Xiaojian Yuan
 * @Date: 2022-04-18 18:17:43
 * @Description: 会场安排问题
 * 贪心策略: 每次选择开始时间早的，看看是否可以安排在某个相容的会场中
 * @FilePath: /cpp/algorithm/algorithm_homework/4-1/4-1.cc
 */

#include <iostream>
#include <algorithm>
using namespace std;

const int maxn = 10000;

struct node
{
    int begin;
    int end;
} activity[maxn];

bool cmp(node a, node b)
{
    return a.begin < b.begin;
}

int main(int argc, char const *argv[])
{
    int k;
    cin >> k;
    for (int i = 0; i < k; i++)
    {
        cin >> activity[i].begin >> activity[i].end;
    }
    // 按活动的开始时间排序
    sort(activity, activity + k, cmp);

    // 存储会场数量
    int res = 1;
    // 存储每个会场中活动的结束时间
    int room[maxn];
    room[1] = activity[0].end;

    // 依次遍历每个活动
    for (int i = 1; i < k; i++)
    {
        int flag = 0;
        // 依次遍历目前已开辟的会场
        for (int j = 1; j <= res; j++)
        {
            // 判断是否存在相容的会场
            if (activity[i].begin >= room[j])
            {
                flag = 1;
                // 存在相容的会场, 更新该会场的结束时间
                room[j] = activity[i].end;
                break;
            }
        }
        // 如果当前没有相容的会场,则开辟一个新会场
        if (!flag)
        {
            res++;
            room[res] = activity[i].end;
        }
    }
    cout << "result: " << res << endl;
    return 0;
}

4.8 最优合并问题

image-20220419142657696

（1）贪心策略

  • 最优合并策略：优先序列长度最小的两个序列进行合并。
  • 最差合并策略：优先序列长度最大的两个序列进行合并。

（2）贪心选择策略

与哈夫曼编码问题等价，设$S$为要合并的序列集合，其中$S_i,S_j$具有最小的序列长度，则存在$S$的最优合并二叉树$T$，使得$S_i$和$S_j$为$T$中最深叶子结点且为兄弟结点。

证明：

假设$S$中的任意两个序列$S_m,S_n$为二叉树$T$的最深叶子且为兄弟。不是一般性，可设$S_m<S_n$，$S_i<S_j$。因为$S_i,S_j$具有最短的序列长度，所以$S_i \leq S_m$，$S_j \leq S_n$。如下图，对二叉树$T$交换叶子$S_m$和$S_i$的位置得到二叉树$T’$，再对$T’$交换$S_n$和$S_j$的位置得到二叉树$T’’$。

image-20220419161732733

设合并二叉树$T$所需比较次数用$B(T)$表示，则有：
$$
B(T) = (S_m+S_n-1)+(S_j+S_m+S_n-1)+(S_j+S_m+S_n+S_i-1)\
B(T’)= (S_i+S_n-1)+(S_j+S_i+S_n-1)+(S_j+S_i+S_n+S_m-1)\
B(T)-b(T’)=2(S_m - S_i) \geq 0
$$
同理可得，$B(T’)-B(T’’) \geq 0$，因此有$B(T) \geq B(T’) \geq B(T’’)$，即$T’’$表示合并二叉树为最优的 ，此时序列长度最短的两个序列$S_i,S_j$为最深叶子结点且为兄弟。

（3）最优子结构

设原问题的最优合并二叉树为$T$，$S_i,S_j$是二叉合并树$T$的叶子结点且为兄弟，$Z=S_i+S_j$是它们的父亲结点，则树$T’=T-{S_1,S_2}$是子问题$S’=S-{S_1,S_2} \cup {Z}$的最优合并二叉树。

反证：

若子问题$S’$存在一个更优的合并二叉树$T’’$，即$B(T’’) \lt B(T’)$ ，那么将会有$B(T’’-{Z} \cup {S_1,S_2}) \lt B(T’-{Z} \cup {S_1,S_2})=B(T)$，与$T$是原问题的最优解矛盾。

（4）时间复杂度

实现上可以通过优先级队列，主要的复杂度来自于队列的排序过程，即$O(nlogn)$

（5）代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
/*
 * @Author: Xiaojian Yuan
 * @Date: 2022-04-19 14:39:07
 * @Description: 最优合并问题
 * 最少合并次数: 每次合并序列长度最短的两个序列
 * 最多合并次数: 每次合并序列长度最长的两个序列
 * @FilePath: /cpp/algorithm/algorithm_homework/4-2/4-2.cc
 */

#include <iostream>
#include <queue>
using namespace std;

int main()
{
    int k;
    cin >> k;
    // 升序队列
    priority_queue<int, vector<int>, greater<int>> small;
    // 降序队列
    priority_queue<int, vector<int>, less<int>> big;

    for (int i = 0; i < k; i++)
    {
        int tmp;
        cin >> tmp;
        big.push(tmp);
        small.push(tmp);
    }
    int max_res = 0, min_res = 0;
    int m = 0, n = 0;
    while (big.size() != 1)
    {
        // 取出序列长度最大的两个序列进行合并
        m = big.top();
        big.pop();
        n = big.top();
        big.pop();
        // 合并所需的比较次数
        max_res += (m + n - 1);
        // 更新当前序列集合
        big.push(m + n);
    }
    while (small.size() != 1)
    {
        // 取出序列长度最小的两个序列进行合并
        m = small.top();
        small.pop();
        n = small.top();
        small.pop();
        // 合并所需的比较次数
        min_res += (m + n - 1);
        // 更新当前序列集合
        small.push(m + n);
    }

    cout << max_res << " " << min_res << endl;
    return 0;
}

4.9 汽车加油问题

image-20220419153654224

（1）贪心策略

如果当前汽车的油足够行驶到下一个加油站，则不加油，否则加油，即让汽车行驶尽可能远的距离再加油。

（2）贪心选择性质

设汽车在加满油行驶的$n$千米内任取两个加油站$X$和$Y$，且它们距起点的距离分别为$x$千米和$y$千米($x \lt y$)。那么，若汽车在加油站$Y$加油不足以到达终点，那么其在加油站$X$加油也必然不能到达终点，因为$x+n \lt y+n$，而在$Y$加油比在$X$加油可以多行驶$y-n$千米。为了使加油次数尽可能的少，据需要使汽车每次加完油都行驶尽可能远的距离。

（3）最优子结构

设原问题的最优解为$A[1:k]$，表示从起点（第$0$个加油站）到终点（第$k+1$个加油站）汽车加油问题。若在第$i$个加油站进行加油，那么总共的加油次数就等于子问题$A[1:i]$的加油次数，加上子问题$A[i+1:k]$的加油次数，再加上$1$，并且$A[1:i]$和$A[i+1:k]$均具有最优子结构。

反证：如果存在更优的加油位置$i’$使$A[1:i’]$或$A[i’+1:k]$的存在更优的解，那么用它替换$A[1:i]$或$A[i+1:k]$得到的$A[1:k]$计算量也会比定义的最优解次数更少，导致矛盾。

（4）代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
/*
 * @Author: Xiaojian Yuan
 * @Date: 2022-04-19 19:55:16
 * @Description: 汽车加油问题
 * @FilePath: /cpp/algorithm/algorithm_homework/4-9/3-9.cc
 */

#include <iostream>
using namespace std;

int main(int argc, char const *argv[])
{
    int n, k;
    cin >> n >> k;
    int gas[k + 1];
    for (int i = 0; i <= k; i++)
    {
        cin >> gas[i];
    }
    for (int i = 0; i <= k; i++)
    {
        if (gas[i] > n)
        {
            cout << "No Solution" << endl;
            return 0;
        }
    }
    int sum = 0, res = 0;
    for (int i = 0; i <= k; i++)
    {
        sum += gas[i];
        if (sum > n)
        {
            res++;
            i--;
            sum = 0;
        }
    }
    cout << res << endl;
    return 0;
}

（5）时间复杂度

只需要一次循环即可得到答案，时间复杂度为$O(n)$。

4.10 磁盘文件最优存储问题

image-20220419210315806

image-20220419210325545

（1）贪心策略

优先将检索概率大的文件存储在磁盘的中间磁道上。

具体的，假设针对文件${f_1,f_2,\dots,f_n}$按检索概率非增序排列，那么首先将$f_1$放在中间磁道($n/2$)上，然后将$f_2$和$f_3$分别存放到$f_1$的左右两侧磁道，再将$f_4$存放在$f_2$的旁边，$f_5$存放在$f_3$的旁边， 以此类推。

（2）正确性证明

对于期望时间$\sum p_i p_j d(i,j)$ ，$p_i p_j$是根据输入固定的，我们能优化的为$d(i,j)$，因此对于更大的$p_i p_j$希望其能够具有更小的$d(i,j)$,即概率大的两个磁道尽量靠近。

假设$n$文件中检索概率最大的三个文件分别为$f_i,f_j,f_k (p_i > p_j > p_k)$，设$D_{ijk},D_{jik},D_{jki}$分别表示将概率检索概率最大的文件$f_i$分别放在最左侧，中间和最右侧时的检索时间，可以得到：
$$
D_{ijk}=p_i p_j d + p_i p_k 2d + p_j p_k d \
D_{jik}=p_j p_i d + p_j p_k 2d + p_i p_k d \
D_{jki}=p_j p_k d + p_j p_i 2d + p_k p_i d \
D_{jik}-D_{ijk}=p_j p_k d - p_i p_k d=(p_j -p_i)p_k d < 0 \
D_{jik}-D_{jki}=p_j p_k d - p_j p_i d = (p_k - p_i) p_j d < 0 \
$$
得到$D_{jik}<D_{ijk}，D_{jik}<D_{jki}$，也就是将检索概率最大的文件$f_i$存放在磁道中间位置具有更小的检索时间，满足贪心选择策略。

（3）代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
/*
 * @Author: Xiaojian Yuan
 * @Date: 2022-04-19 21:54:23
 * @Description: 磁盘文件最优存储问题
 * 贪心策略: 将检索概率大的文件优先放在靠近中间的磁道上。
 * @FilePath: /cpp/algorithm/algorithm_homework/4-4/4-4.cc
 */
#include <iostream>
#include <algorithm>
using namespace std;

bool cmp(int a, int b)
{
    return a > b;
}
int main(int argc, char const *argv[])
{
    int n, sum = 0;
    cin >> n;
    int a[n], b[n];
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
        sum += a[i];
    }
    sort(a, a + n, cmp);
    // 将检索概率大的存放在靠近中间位置的磁道
    int mid = n / 2;
    b[mid] = a[0];
    for (int i = 1, k = 1; i < n; i++, k++)
    {
        b[mid - k] = a[i];
        i++;
        b[mid + k] = a[i];
    }

    // 计算期望检索时间
    double res = 0;
    for (int i = 0; i < n; i++)
    {
        for (int j = i + 1; j < n; j++)
        {
            res += (b[i] * 1.0 / sum) * (b[j] * 1.0 / sum) * (j - i);
        }
    }
    cout << res << endl;
    return 0;
}

（4）时间复杂度

对检索概率排序需要$O(nlogn)$，将文件存放到磁道上需要$O(n)$，计算期望检索时间需要$O(n^2)$.

5 回溯法

  • 回溯法的主要思想为深度优先搜索。

  • 解向量：回溯法希望一个问题的解能够表示成一个 $n$ 元式 $(x_1 ,x_2, \dots, x_n)$ 的形式

  • 常用剪枝函数：

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

  • 解空间：子集树与排列树

    <img src=”data:image/svg+xml,“ alt=”image-20220526114359851” style=”zoom:40%;” />

5.1 装载问题

问题同4.2，有一批共 $n$ 个集装箱要装上 2 艘载重量分别为 $c_1$ 和 $c_2$ 的轮船， 其中集装箱 $i$ 的重量为 $w_i$ ，且 $\sum_{i=1}^{n} w_i \leq c_1 + c_2$。装载问题要求确定是否有一个合理的装载方案可将这个集装箱装上这 2 艘轮船；如果有，找出一种装载方案？

思路：容易证明，如果一个给定装载问题有解，则采用下面的策略可得到最优装载方案：先将第一艘轮船尽可能装满，然后将剩余的集装箱装上第二艘轮船。将第一艘轮船尽可能装满等价于选取全体集装箱的一个子集， 使该子集中集装箱重量之和最接近 $c_1$。

  • 解空间：子集树。

  • 左儿子表示选择装入当前集装箱，需要判断可行性；右儿子表示不选择装入当前集装箱，总是可行的，但是通过限界函数判断其子树是否存在更优解，不存在则剪去。

  • 可行性约束函数：选择当前元素后，选择装入的集装箱总重量不超过轮船载重量，$\sum_{i=1}^{n}w_ix_i \leq c_1$。

  • 限界函数：当前载重量 $\text{cw}$ + 剩余集装箱的重量 $\text{r}$ $\leq$ 当前最优载重量$\text{bestw}$，也就是 $cw + r \leq bestw$ 时，可以剪去右子树。

  • 搜索过程：

5.2 批处理作业调度

image-20220620165033935

解空间：排列树

优化目标：所有作业在机器2上完成的时间和最小 $\min{\sum_{i=1}^{n}F_{2i}}$

搜索过程：

  • 当 $i>n$ 时，算法搜索至叶子结点，得到一个新的作业调度方案。此时算法适时更新当前最优值和相应的当前最佳调度。
  • 当 $i<n$ 时，当前扩展结点位于排列树的第 $(i-1)$ 层，此时算法选择下一个要安排的作业，以深度优先方式递归的对相应的子树进行搜索，对不满足上界约束的结点，则剪去相应的子树。
  • 上界约束，当前在机器二上的完成时间和已经会超过当前最优解，即该子树不存在更优解。
  • 处理作业 $i$ 时，比较 $i$ 在机器1上的结束时间，和作业 $i-1$ 在机器2上的结束时间，较大的那个作为第 $i$ 个任务在机器2上的开始时间。
  • 最坏情况下复杂度 $O(n!)$
image-20220526153739887 image-20220620165048914

5.3 符号三角形

image-20220620165105013

  • 解空间：子集树。用 n 元组 $x[1:n]$ 表示符号三角形的第一行，每个元素选择 + 或 -。

  • 可行性约束函数：当前符号三角形所包含的 “+” 个 “-” 个数均不超过 $n(n+1)/4$

  • 最坏情况时间复杂度 $O(n 2^n)$

5.4 n 后问题

image-20220526161158148

  • 解空间：排列树，解向量为 $x[1:n]$ 的排列，其中 $x[i]$ 表示皇后 $i$ 放在棋盘的第 $i$ 行的第 $x[i]$ 列。

  • 可行性约束函数：显然各皇后不在同一行，还需要不在同一列（$x[i] \neq x[j]$），以及不在同一对角线（$|i-j| \neq |x_i - x_j|$）。

  • 搜索过程：当 $i>n$，到达叶结点，得到n后问题的一个可行解。当 $i\leq n$时，对当前扩展结点的每个儿子结点进行可行性的检查，并以深度优先的方式递归地对可行子树进行搜索，或剪去不可行子树，

5.5 0-1背包问题

  • 解空间：子集树。

  • 每一个扩展结点左儿子表示当前物品装入背包，符合可行性约束才进入左子树；右儿子表示不装入背包，只有存在更优解时才进入右子树。

  • 可行性约束函数：当前装入物品的总重量不超过背包容量，即 $\sum_{i=1}^{n}w_ix_i \leq c$

  • 上界函数：当前子树所具有的总价值，不会超过当前最优解，即 $\sum_{j=1}^{i}w_iv_i + r \leq bestp$

  • 计算更好的上界的方法是：将剩余物品根据单位重量价值排序，然后依次装入物品，直到装不下时，再装入该物品的一部分而装满背包，此时得到的价值是右子树中解的上界。

image-20220620165129641

5.6 最大团问题

image-20220620165141622
  • 解空间：子集树
  • 可行性约束函数：顶点 $i$ 到已选入顶点集中每一个顶点都有边相连
  • 上界函数：有足够多的可选择顶点 使得算法有可能在右子树中找到更大的团
  • 搜索过程：设当前扩展结点 $Z$ 位于解空间树的第 $i$ 层，进入左子树前，先确认从顶点 $i$ 到已选入的顶点集中每个顶点都有边相连；进入右子树前，先确认还有足够多的可选择顶点，使算法有可能在右子树中找到更大的团。
  • 复杂度 $O(n 2^n)$

5.7 图的m着色问题

image-20220620165204042

  • 解空间：排列树，是一个 $n+1$ 层的完全 $m$ 叉树。用$x[1:n]$ 表示解向量，其中 $x[i]$ 表示顶点 $i$ 所着颜色为 $x[i]$，第 $i$ 层中每个结点有$m$个儿子，每个儿子对应于 $x[i]$ 的 $m$ 个可能的着色之一。

  • 可行性约束函数：顶点 $i$ 与已着色的相邻顶点颜色不重复

  • 搜索过程：

    • 当 $i > n$ 时，算法搜索到叶结点，此时得到一个新的着色方案。
    • 当 $i \leq n$ 时，当前扩展结点$Z$ 有 $m$ 个儿子结点 $x[i]$。对当前扩展结点 $Z$ 的每个儿子结点，用可行性约束函数判断其可行性，并以深度优先的方式递归地对可行子树进行搜索，或剪去不可行子树。
image-20220620165215409

5.8 旅行售货员问题

image-20220620165234301
  • 解空间：排列树，解向量为 $x[1:n]$ 的所有排列。
  • 可行性约束函数：是否存在一条从顶点 $x[i-1]$ 到顶点 $x[i]$ 的边，即是否存在相连路径；如果 $i=n$ 则还需要判断师傅和一条从顶点 $x[n]$ 到 顶点 1的边，即是否构成一个回路。
  • 上界约束函数：当前已走过路径的费用是否优于已找到的当前最优回路费用 bestc。
  • 搜索过程：
    • 当 $i=n$ 时，当前扩展结点时排列树叶结点的父结点。此时，通过可行性约束判断当前路线是否存在一条满足要求的回路，若存在，则得到一个可行解。然后判断，该可行解的费用是否优于当前已找到的最优路线费用。如果是，则更新当前最优值和最优解。
    • 当 $i < n$ 时，当前扩展结点位于排列树的第 $i-1$ 层。用可行性约束判断图 $G$ 中是否存在从顶点 $x[i-1]$ 到顶点 $x[i]$ 的边，$x[1:i]$ 构成图G的一条路径，且当 $x[1:i]$ 的费用小于当前最优值时算法进入排列树的第 $i$ 层，否则剪去相应的子树。

5.9 连续邮资问题

image-20220526174402955
  • 解向量：用 $n$ 元组 $x[1:n]$ 表示 $n$ 种不同的邮票面值，约定它们从小到大排列。$x[1]=1$ 是唯一的选择，因为要贴出1的邮资。
  • 可行性约束函数：已选定 $x[1:i-1]$，最大连续邮资区间是 $[1:r]$，接下来 $x[i]$ 的可取值范围是 $[x[i-1]+1:r+1]$
image-20220526174943356

5.10 最小电路板长度排列问题

image-20220505155828933

该问题的解空间是一个排列树。当$i=n$到达叶节点时，所有电路板已排列，遍历每一个连接块，并对每一个连接块都分别从排列的左侧和右侧对电路板进行编列，从而找到该连接块的长度。我们记录所有连接块中的最大长度，并比较它与当前最优值的大小，如果小于当前最优值，则对最优值和最优解进行更新。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100

#include <iostream>
using namespace std;

int n; //电路板数量
int m; //连接块数量
int B[25][25];   //连接块数组
int best_len=999999;   // 最优值
int best_x[25]; // 当前最优解
int x[25];      //当前解
int tmp_len;

void traceback(int t)
{
    int l, r, tmp;
    if (t == n)     //到达叶节点，得到一个排列
    {
        //计算当前排列的长度
        tmp_len = 0;
        for (int i = 0; i < m; i++) //遍历连接块
        {   
            // 从左侧遍历第i个连接块的电路板
            for (int j = 0; j < n; j++) 
            {
                // 找到连接块i在当前排列最左侧的电路板j
                if (B[x[j]][i] == 1)
                {
                    l = j;
                    break;
                }
            }
            // 从右侧遍历第i个连接块的电路板
            for (int j = n - 1; j >= 0; j--)
            {
                // 找到连接块i在当前排列最左侧的电路板j
                if (B[x[j]][i] == 1)
                {
                    r = j;
                    break;
                }
            }
            // 记录连接板的最大长度
            if (tmp_len < r - l) 
            {
                tmp_len = r - l;
            }
        }
        // 要使最大长度最小
        if (tmp_len < best_len) 
        {
            // 记录最优值
            best_len = tmp_len;
            // 记录最优解
            for (int i = 0; i < n; i++)
            {
                best_x[i] = x[i];
            }
        }
    }
    
    // 没有到达叶节点
    for (int i = t; i < n; i++)
    {
        // swap(x[i], x[t]);
        tmp = x[i];
        x[i] = x[t];
        x[t] = tmp;
        traceback(t + 1);
        // swap(x[i], x[t]);
        tmp = x[i];
        x[i] = x[t];
        x[t] = tmp;
    }
}


int main(int argc, char const *argv[])
{
    cin >> n >> m;
    for (int i = 0; i < n;i++)
    {
        for (int j = 0; j < m; j++)
        {
            cin >> B[i][j];
        }
    }
    // 初始化排列
    for (int i = 0; i < n;i++)
    {
        x[i] = i;
    }
    traceback(0);
    cout << best_len << endl;
    for (int i = 0; i < n;i++)
    {
        cout << best_x[i] + 1 << " ";
    }
    return 0;
}

5.11 无和集问题

image-20220506163309034

解空间为一棵子集树，树的每一层表示一个子集。

可行性条件：对于一个已有的递增子集，现在要判断新增的数能否加入该子集中。如果通过判断“任意两个数的和不在该子集中”，那么就需要双重循环遍历进行判断。因此，可以转换一下思路，让新增的数与子集中每一个数做减法，若如果它们的差值也存在于该子集中，则说明该数不能插入该集合中，这种方法只需要一次循环即可判断。

思路：

对于每一个新增的数，首先进行可行性的判断，判断其是否能加入到当前层所表示的子集中：

  • 如果不能插入当前层表示的子集，就继续判断该新增的数其能否插入到下一层所表示子集中。
  • 如果可以插入当前层表示的子集，那么就存在两个儿子节点，分别为插入当前子集和不插入当前子集。
    • 如果选择插入当前子集，则从第一层开始再将判断下一个新增的数。
    • 如果选择不插入当前子集，则继续判断是否将该数插入下一个子集。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
// 无和集问题
#include <iostream>
using namespace std;

const int MAXN = 100;

/*
best_res[n][0]表示第n个集合中的元素个数
从best_res[n][1]到best_res[n][best_res[n][0]]表示集合n中具体的数
inSet[i][j] 表示第i个子集中是否有j这个元素
*/
int n;
int best_res[MAXN][MAXN];
int tmp_res[MAXN][MAXN];
int best_k, tmp_k = 1;
bool inSet[MAXN][MAXN] = {false};

// 解空间树的每一层代表一个子集，判断当前的tmp_k是否能够插入到这个集合中
void traceback(int t)
{
    if (t == n)
    {
        //当前k不如最优k，则返回
        if (tmp_k <= best_k)
            return;
        // 否则更新最优值
        best_k = tmp_k;
        // 更新最优解
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j <= tmp_res[i][0]; j++)
            {
                best_res[i][j] = tmp_res[i][j];
            }
        }
        return;
    }
    else
    {
        // 判断当前的tmp_k是否能够插入当前层的子集
        bool flag = true;
        // 遍历该层所表示的子集
        for (int i = 1; i <= tmp_res[t][0]; i++)
        {
            /*
            可行性条件: (任意两个数的差值不在这个集合中)
            tmp_k减去这个元素后tmp_res[t][i]得到的值已经在这个集合中，并且不是这个数本身(排除掉集合中的0)，flag=False
            tmp_k减去这个元素后tmp_res[t][i]得到的值不在这个集合中，flag=True
            */
            if (inSet[t][tmp_k - tmp_res[t][i]] && tmp_k - tmp_res[t][i] != tmp_res[t][i])
            {
                flag = false;
            }
        }
        // 如果不能插入当前层的集合，那么继续判断能否插入到下一层的集合中
        if (!flag)
        {
            traceback(t + 1);
        }
        //如果可以插入当前层的集合(选择插入或者不插入)
        else
        {
            // 如果插入当前集合（左子树）
            tmp_res[t][0]++;                   // 该集合中元素数量加1
            tmp_res[t][tmp_res[t][0]] = tmp_k; // 将tmp_k加入到该集合的最后
            inSet[t][tmp_k] = true;            // 更新标记，该元素在该集合中
            tmp_k++;                           // 当前tmp_k所表示的数字已分配到集合，考虑tmp_k+1

            //对tmp_k+1，重新从第0个集合开始判断
            traceback(0);

            //如果不插入当前集合
            tmp_res[t][0]--;
            tmp_k--;
            inSet[t][tmp_k] = false;
            traceback(t + 1); // 是否插入下一个集合
        }
    }
}
int main()
{
    cin >> n;
    traceback(0);
    cout << --best_k << endl;
    for (int i = 0; i < n; i++)
    {
        for (int j = 1; j <= best_res[i][0]; j++)
        {
            cout << best_res[i][j] << " ";
        }
        cout << endl;
    }
    return 0;
}

5.12 工作分配问题

image-20220506183739123

解空间为一个经典的排列树，得到最优解为x[n]，表示将第i个工作分配给第x[i]个人去做，在到达叶节点得到一个排列后，只需要根据当前排列查询每个工作i的所需的费用c[i][x[i]]进行累加，即可得到总费用。如果总费用小于最优值，则更新当前最优值和最优解。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include <iostream>
using namespace std;

const int MAXN = 25;
int n;
int c[MAXN][MAXN];             // c[i][j]表示工作i分配个第j个人所需的费用
int tmp_x[MAXN], best_x[MAXN]; // best_x[i] 表示第i个工作由第best_x[i]个人完成,
int best_res = 999, tmp_res;
void traceback(int t)
{
    if (t == n)
    {
        tmp_res = 0;
        // 计算当前排列的所需要的费用
        for (int i = 0; i < n; i++)
            //第i个工作由第x[i]个完成所需要的费用
            tmp_res += c[i][tmp_x[i]];
        if (tmp_res < best_res)
        {
            best_res = tmp_res;
            for (int i = 0; i < n; i++)
                best_x[i] = tmp_x[i];
        }
    }
    else
    {
        for (int i = t; i < n; i++)
        {
            int tmp;
            tmp = tmp_x[i];
            tmp_x[i] = tmp_x[t];
            tmp_x[t] = tmp;
            traceback(t + 1);
            tmp = tmp_x[i];
            tmp_x[i] = tmp_x[t];
            tmp_x[t] = tmp;
        }
    }
}
int main()
{
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            cin >> c[i][j];
        }
    }
    // 初始化排列
    for (int i = 0; i < n; i++)
    {
        tmp_x[i] = i;
    }
    traceback(0);
    cout << best_res << endl;
    for (int i = 0; i < n; i++)
        cout << best_x[i] + 1 << " ";
    return 0;
}

5.13 拉丁矩阵问题

image-20220506190719081

共有n种宝石，排列成m*n的矩阵，因此每一行均为$n$种组成的排列，解空间为排列树。对矩阵的每一行进行全排列，同时满足可行性条件，即该行与之前所有行的每一列没有形状重复的宝石。

因此，用函数ok(r,c)判断第c列的前r行是否存在重复的宝石，回溯方法traceback(r,c)对每一行进行排列，使用排列树的框架，没有优化目标，找出所有可行解即可，当搜索到最后一行最后一列时，可行解的数量加一。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
/*
拉丁矩阵问题
n种宝石,m*n的矩阵,每一行是n个宝石的一个排列
*/
#include <iostream>
using namespace std;
const int MAXN = 100;
int m, n;
int matrix[MAXN][MAXN];
int res;

// 判断第c列的前r行是否有同一种宝石
bool ok(int r, int c)
{
    for (int i = 0; i < r; i++)
    {
        if (matrix[i][c] == matrix[r][c])
        {
            return false;
        }
    }
    return true;
}

void traceback(int r, int c)
{
    int tmp;
    //  对每一行的n个宝石进行排列
    for (int i = c; i < n; i++)
    {
        // swap列
        tmp = matrix[r][c];
        matrix[r][c] = matrix[r][i];
        matrix[r][i] = tmp;
        // 判断该行的排列是否与上面的行有重复的列
        if (ok(r, c))
        {
            if (r == m - 1)     // 到达最后一行
            {
                if (c == n - 1) // 到达最后一列
                {
                    res++;      // 获得一个可行解
                    return;
                }
                else             // 未到达最后一列
                {
                    traceback(r, c + 1); //  继续判断下一列
                }
            }
            else // 未到达最后一行
            {
                if (c == n - 1) // 到达某一行的最后一列
                {
                    traceback(r + 1, 0);
                }
                else            
                {
                    traceback(r, c + 1);
                }
            }
        }

        tmp = matrix[r][c];
        matrix[r][c] = matrix[r][i];
        matrix[r][i] = tmp;
    }
}
int main()
{
    cin >> m >> n;
    for (int i = 0; i < m; i++)
    {
        for (int j = 0; j < n; j++)
        {
            // 初始化每一行都是1,2,...,n的排列
            matrix[i][j] = j + 1;
        }
    }
    traceback(0, 0);
    cout << res << endl;
    return 0;
}

6 分支限界法

  • 求解目标不同

    • 回溯法找出解空间中满足约束条件的所有解。
    • 分支限界法找出满足约束条件的一个解，或是在满足约束条件的解中找出某种意义下的最优解

  • 搜索方式不同

    • 回溯法：深度优先搜索
    • 分支限界法：广度优先搜索或最小耗费（最大效益）优先

  • 活结点扩展方式

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

（2）常用的两种分支限界法

  • 队列式 (FIFO) 分支限界法
    • 按照队列先进先出（FIFO）原则选取下一个节点为扩展节点
  • 优先队列式分支限界法
    • 按照优先队列中规定的优先级选取优先级最高的节点成为当前扩展节点
    • 在搜索解空间过程中增加了启发式方法，并通过优先级数值体现

6.1 单源最短路径问题

image-20220620164839384

  • 以当前结点的路径长度作为优先级建立最小堆，从而实现活结点的优先级队列。

  • 算法从图 G 的源顶点 s 和空优先队列开始，结点 s 被扩展后，它的儿子结点被依次插入堆中

  • 从活结点列表中取出具有最小当前路径长度的结点作为当前扩展结点，并依次检查与当前扩展结点相邻的所有顶点：

    • 如果从当前扩展结点 i 到顶点 j 有边可达（可行性约束）
    • 从源出发，途经顶点 i 再到顶点 j 的所相应的路径的长度小于当前最优路径长度（上界约束），否则剪去改结点为根的子树。
    • 则将该顶点作为活结点插入到活结点优先队列中

  • 结点的扩展过程一直继续到活结点优先队列为空时为止

6.2 装载问题

解空间为子集树，节点的左子树表示将此集装箱装上船，右子树表示不将此 集装箱装上船。

（1）基于队列的分支限界

  • 检测当前扩展结点的左儿子是否为可行结点（可行性约束，即不超过轮船载重量），如果是则加入到活结点列表中。
  • 将其右儿子结点加入到活结点队列中 ，右儿子结点一定是可行结点，但是需要用限界函数判断是否存在更优解。
    • 设 bestw 是当前最优解，ew 是当前扩展结点所相应的重量，r 是剩 余集装箱的重量
    • 则当 ew+r $\leq$ bestw 时，可将其右子树剪去，因为此时若要船装最多z集装箱，就应该把此箱装上船
  • 另外，为了确保右子树成功剪枝，应该在算法每一次进入左子树的 时候更新 bestw 的值

（2）基于优先级队列的分支限界

  • 用最大优先队列存储活结点表
    • 活结点 x 在优先队列中的优先级定义为从根结点到结点 x 的路径所相应的载重量再加上剩余集装箱的重量之和
    • 优先队列中优先级最大的活结点成为下一个扩展结点
    • 以结点 x 为根的子树中所有结点相应的路径的载重量不超过它的优先级
    • 子集树中叶结点所相应的载重量与其优先级相同
  • 优先队列式分支限界的终结
    • 一旦有一个叶结点成为当前扩展结点，则可以断言该叶结点所相应的解即为最优解，此时可终止算法

6.3 布线问题

FIFO队列式分支限界法：

  • 从起始位置 a 开始将它作为第一个扩展结点
  • 与扩展结点相邻并且可达的方格成为可行结点（可行性约束），将其加入到活结点队列中，并且将这些方格标记为 1。
  • 算法从活结点队列中取出队首元素作为下一个扩展结点，并将与 当前扩展结点相邻且未标记过的方格标记为 2，并存入活结点队列。
  • 一直继续到算法搜索到目标方格 b 或活结点队列为空

6.4 0-1背包问题

要对输入数据进行预处理，将各物品依其单位重量价值从大到小进行排列

优先级队列分支限界法：

  • 优先级定义为：“已装入的物品价值”加上“剩下最大单位重量价值的物品装满剩余容量”的价值和，也就是当前结点可能装入背包的价值上限。

  • 可行性约束：装入该物品后的重量是否超过背包总容量

  • 上界约束：当前已装入的物品价值加上用剩余最大单位重量价值的物品装满剩余容量的价值和，是否超过当前最优价值（因为已经按单位价值排序，因此直接按顺序装满背包即可）。

  • 首先，检查当前扩展结点的左儿子是否满足可行性约束，如果左儿子是可行结点，则将其加入到活结点优先队列中。

  • 当前扩展解的右儿子一定是可行结点，仅当右儿子结点满足上界约束时，才将其加入到子集树和活结点优先队列中。

  • 不断从活结点列表中取出队首元素作为扩展结点，直到到达叶结点得到问题的最优值。

6.5 旅行售货员问题

某售货员要到若干城市去推销商品，已知各城市之间的路程(或旅费)，他要选定一条从驻地出发，经过每个城市一 次，最后回到驻地的路线，使总的路程(或总旅费)最小。

  • 解空间为排列树，排列树，解向量为 $x[1:n]$ 的所有排列。

  • 优先级定义从源结点到当前结点路程所需的费用加上当前扩展结点最小出边费用，用最小堆实现。

  • 可行性约束：对于当前扩展结点 $i$，是否存在一条从顶点 $x[i-1]$ 到顶点 $x[i]$ 的边，即是否存在相连路径；如果 $i=n$ 则还需要判断师傅和一条从顶点 $x[n]$ 到 顶点 1的边，即是否构成一个回路。

  • 上界约束函数：当前已走过路径的费用加上当前扩展结点最小出边费用，是否优于已找到的当前最优回路费用 bestc。

  • 搜索过程：

    • 当 $s=n-2$，即当前扩展结点时排列树中某个叶结点的父结点。判断该叶结点是否可以构成一条可行回路（满足可行性约束），并且费用小于当前最小费用（满足界限约束），则将该叶结点 插入优先队列中，否则舍去该叶结点。

    • 当 $s \lt n-2$，产生当前扩展结点的所有儿子结点，对于每一个儿子结点，判断是否满足可行性约束（即与剩下的顶点存在相连的边）。对于每一个可行的儿子结点，再判断其是否满足界限约束（当前扩展结点的每个儿子结点，计算出其路径所需的费用加上该儿子结点最小出边的费用），若小于最优解，则将该可行儿子结点加入到活结点优先队列中。

    • while循环的终止：条件是排列树的一个叶结点成为当前扩展结点，当 $s=n-1$ 时，已找到的回路前缀是 $x[0:n-1]$，已包含所有 $n$ 个顶点。当 $s=n-1$ 时，相应的扩展结点表示叶结点，剩余活结点不小于已找到回路的费用，算法终止。

6.6 0-1背包问题的栈式分支限界

image-20220510155552789

首先根据物品的单位价值进行进行非升序排列。算法不断扩展结点，首先检查当前扩展结点的左儿子是否为可行结点，可行性约束为已入背包的重量加上该结点重量后是否超过背包总重量，如果左儿子是可行结点，则将其加入到活结点栈中。当前扩展结点的右儿子一定是可行结点，判断其是否符合上界约束，即其所包含的子数存在更优解时才将其加入到活结点栈中。

分支限界法与回溯法的区别在于，分支限界法中每一个活结点只有一次机会，且活结点一旦成为扩展结点，就一次性产生其所有儿子结点。此后，从活结点表中取下一结点作为当前扩展结点，直到找到所需的解或活结点表为空，其主要思想为广度遍历优先。而回溯法中的结点有可能多次成为活结点，其主要思想为深度遍历优先。

6.7 最小长度电路板排列问题

image-20220510155611347

image-20220510155619887

该问题的解空间是一颗排列树，用 BoardNode类表示排列树的每个结点，其中包含 x 表示相应结点的电路板排列，s 表示该结点已确定的电路板排列x[1:s]，cd表示当前的长度，数组low和high分别表示每个连接块第一个和最后一个电路板的位置，当需要计算当前排列的最小长度是，只要依次将high和low中的元素做减法，并取其中最小值即可。

当使用队列式分支限界法时，依次对排列树内部结点进行扩展，当s=n-1时，已排定n-1块电路板，当前扩展结点是排列树中叶结点的父结点，x表示相应于该叶结点的电路板排列，计算出此时x的长度，若小于当前的最优值，则更新最优值和最优解。当s<n-1时，算法依次产生当前扩展结点的所有儿子结点。对于每一个儿子结点，计算出其长度，若小于当前的最优值，则将该儿子结点插入到活结点队列中，否则舍去该儿子结点。do-while循环依次从活结点队列中取出结点作为当前扩展结点，直到队列为空时，算法结束。

当使用优先级队列分支限界法时，用当前结点的长度cd作为优先级插入优先级队列中（最小堆）。do-while循环依次从活结点优先级队列中取出结点作为当前扩展结点，如果当前扩展结点的长度cd不小于当前最小长度，则优先级毒烈中其余活结点都不可能导致最优解，算法结束。

6.8 最小权顶点覆盖问题

image-20220510155638419

  • 该问题的解空间是一个子集树，以当前扩展结点的权重作为优先级建立最小堆，从而实现活结点优先级队列。

  • 设组成顶点覆盖的集合为U，约束条件为集合 U中的点集能够完成对图G的顶点覆盖。具体做法可以每个活结点开辟一个数组c，每次将顶点i加入到集合U时，依次判断n个顶点是否与i有相连的边，如果顶点j与顶点i有边，则将c[j]加一，若最终c[j]=0，则说明当前U并没有覆盖到顶点j。利用数组c，可以判断当前扩展结点是否完成顶点覆盖，即遍历所有顶点j(1<=j<=n)，若 j 既不是 U 中的点 (E.x[j]=0)，也没有与 U 中的顶点相连 (E.c[j]=0），则说明未完成顶点覆盖。

  • 当 i>n时，到达叶结点，判断当前最优解是否完成了顶点覆盖，若已完成则更新最优值和最优解。

  • 当i<n时，对于当前扩展结点，如果没有完成顶点覆盖，才有必要将左儿子加入到活结点队列中，否则无需选择左儿子来进一步增加集合U中的权重；该问题无法设定界限约束，右儿子则直接加入到活结点队列中，因为如果只选择右儿子，那么覆盖集顶点权重一定更小，但是却不一定能够完成顶点覆盖

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
// 最小权顶点覆盖问题
#include <iostream>
using namespace std;

#include "MinHeap.h"

class HeapNode
{
    // //求解最小权覆盖问题的类,融合了所有函数和所需的参数
    friend class DealNode; //将VC声明为友元类，即可以在VC类中访问HeapNode类中的私有成员
public:
    operator int() const { return cn; } // 定义优先级(最小堆)
private:
    // i表示当前层级，cn表示当前权重，x表示当前解，
    // c[i]=0，表示顶点i既不在覆盖集合U中，也不存在U中的顶点与其相连，说明该顶点i未被覆盖
    int i, cn, *x, *c;
};

class DealNode
{
    friend int MinCover(int **, int[], int); //将MinCover声明为友元函数，既可以在MinCover中访问该类的私有成员
private:
    void BBVC();
    bool cover(HeapNode E); //判断当前图E是否全部覆盖了
    void AddLiveNode(MinHeap<HeapNode> &H, HeapNode E, int cn, int i, bool ch);
    int **a, n, *w, *bestx, bestn;
    // a表示邻接矩阵，n表示结点数量，数组w存储结点权重，bestw表示最优解， bestn表示最优值
};

void DealNode::BBVC()
{
    MinHeap<HeapNode> H(10000);
    HeapNode E; // 当前扩展结点
    E.x = new int[n + 1];
    E.c = new int[n + 1];
    // 初始化
    for (int j = 1; j <= n; j++)
    {
        E.x[j] = E.c[j] = 0;
    }
    int i = 1, cn = 0;
    while (true)
    {
        if (i > n) // 到达叶结点
        {
            // 当前扩展结点是否已经完成顶点覆盖
            if (cover(E))
            {
                // 更新最优解和最优值
                for (int j = 1; j <= n; j++)
                    bestx[j] = E.x[j];
                bestn = cn;
                break;
            }
        }
        else // 未到达叶结点
        {
            // 还未完成顶点覆盖，才有必将左儿子加入活结点优先级队列中
            // 如果已经符合顶点覆盖条件了，那就没有必要选择左儿子来增加集合U中的权重了
            if (!cover(E))
                AddLiveNode(H, E, cn, i, 1);
            // 将右儿子加入优先级队列,这里无法进行界限约束，
            // 因为如果只选择右儿子，那么覆盖集顶点权重一定更小，但是不一定能够完成顶点覆盖
            AddLiveNode(H, E, cn, i, 0);
        }
        if (H.IsEmpty())
            break;
        // 从活结点优先级队列中取出扩展结点
        H.RemoveMin(E);
        cn = E.cn;
        i = E.i + 1;
    }
}
// 判断当前图是否完成顶点覆盖
bool DealNode::cover(HeapNode E)
{
    for (int j = 1; j <= n; j++)
    {
        // 如果此时结点j既不是覆盖集合U中的点，也没有U中的点与其相连，则说明存在未覆盖的顶点j
        if (E.x[j] == 0 && E.c[j] == 0)
        {
            return false;
        }
    }
    return true;
}
// 将扩展结点加入到优先级活结点队列中
void DealNode::AddLiveNode(MinHeap<HeapNode> &H, HeapNode E, int cn, int i, bool ch)
{
    // 创建新的堆结点
    HeapNode N;
    N.x = new int[n + 1];
    N.c = new int[n + 1];
    for (int j = 1; j <= n; j++)
    {
        N.x[j] = E.x[j];
        N.c[j] = E.c[j];
    }
    // 第i个顶点是否加入到集合U中
    N.x[i] = ch;
    // 若加入到集合U中
    if (ch)
    {
        // 更新集合U中的顶点总权重
        N.cn = cn + w[i];
        for (int j = 1; j <= n; j++)
        {
            if (a[i][j])
                // 第j个顶点是否与集合U中的顶点i有边相连，若右边则说明该顶点j已被覆盖
                N.c[j]++;
        }
    }
    else
    {
        N.cn = cn;
    }
    N.i = i;
    H.Insert(N);
}

// MinCover完成最小覆盖计算
int MinCover(int **a, int v[], int n)
{
    DealNode Y;
    Y.w = new int[n + 1];
    for (int j = 1; j <= n; j++)
        Y.w[j] = v[j];
    Y.a = a;
    Y.n = n;
    Y.bestx = v;
    Y.BBVC();
    return Y.bestn;
}

int main()
{
    int n, e, u, v; // n结点数,e边数,u,v为结点编号
    cin >> n >> e;

    int p[n + 1]; // 权重
    //邻接矩阵(创建二维数组)
    int **a;
    a = new int *[n + 1];
    for (int i = 0; i <= n; i++)
        a[i] = new int[n + 1];

    for (int i = 0; i <= n; i++)
    {
        p[i] = 0;
        for (int j = 0; j <= n; j++)
        {
            a[i][j] = 0;
        }
    }

    for (int i = 1; i <= n; i++)
    {
        cin >> p[i];
    }
    for (int i = 1; i <= e; i++)
    {
        cin >> u >> v;
        a[u][v] = 1;
        a[v][u] = 1;
    }
    cout << MinCover(a, p, n) << endl;
    for (int i = 1; i <= n; i++)
        cout << p[i] << " ";
    cout << endl;
    return 0;
}

最小堆MinHeap.h的代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
template <class Type>
class MinHeap //最小堆类；
{
public:
    MinHeap(Type a[], int n);   //带两参数的构造函数，在此程序中没有应用；
    MinHeap(int ms);            //构造函数重载，只初始化堆的大小，对堆中结点不初始化；另外，堆元素的存储是以数组
    ~MinHeap();                 //形式，且无父、子指针，访问父亲结点，利用数组标号进行；
    bool Insert(const Type &x); //插入堆中一个元素；
    bool RemoveMin(Type &x);    //删除堆顶最小结点；
    void MakeEmpty();           //使堆为空
    bool IsEmpty();
    bool IsFull();
    int Size();

protected:
    void FilterDown(const int start, const int endOfHeap); //自顶向下构造堆
    void FilterUp(const int start);                        //自底向上构造堆
private:
    Type *heap;
    int maxSize;
    const int defaultSize;
    int currentSize; //堆当前结点个数大小
};

template <class Type>
MinHeap<Type>::MinHeap(int ms) : defaultSize(100)
{
    maxSize = (ms > defaultSize) ? ms : defaultSize;
    heap = new Type[maxSize];
    currentSize = 0;
}

template <class Type>
MinHeap<Type>::MinHeap(Type a[], int n) : defaultSize(100)
{
    maxSize = (n > defaultSize) ? n : defaultSize;
    heap = new Type[maxSize];
    currentSize = n;
    for (int i = 0; i < n; i++)
        heap[i] = a[i];
    int curPos = (currentSize - 2) / 2;
    while (curPos >= 0)
    {
        FilterDown(curPos, currentSize - 1);
        curPos--;
    }
}

template <class Type>
MinHeap<Type>::~MinHeap()
{
    delete[] heap;
}

template <class Type>
void MinHeap<Type>::FilterDown(const int start, const int endOfHeap)
{
    int i = start, j = i * 2 + 1;
    Type temp = heap[i];
    while (j <= endOfHeap)
    {
        if (j < endOfHeap && heap[j] > heap[j + 1])
            j++;
        if (temp < heap[j])
            break;
        else
        {
            heap[i] = heap[j];
            i = j;
            j = 2 * i + 1;
        }
    }
    heap[i] = temp;
}

template <class Type>
void MinHeap<Type>::FilterUp(const int start)
{
    int i = start, j = (i - 1) / 2;
    Type temp = heap[i];
    while (i > 0)
    {
        if (temp >= heap[j])
            break;
        else
        {
            heap[i] = heap[j];
            i = j;
            j = (i - 1) / 2;
        }
    }
    heap[i] = temp;
}

template <class Type>
bool MinHeap<Type>::RemoveMin(Type &x)
{
    if (IsEmpty())
    {
        cerr << "Heap empty!" << endl;
        return false;
    }
    x = heap[0];
    heap[0] = heap[currentSize - 1];
    currentSize--;
    FilterDown(0, currentSize - 1);
    return true;
}

template <class Type>
bool MinHeap<Type>::Insert(const Type &x)
{
    if (IsFull())
    {
        cerr << "Heap Full!" << endl;
        return false;
    }
    heap[currentSize] = x;
    FilterUp(currentSize);
    currentSize++;
    return true;
}

template <class Type>
bool MinHeap<Type>::IsEmpty()
{
    return currentSize == 0;
}

template <class Type>
bool MinHeap<Type>::IsFull()
{
    return currentSize == maxSize;
}

template <class Type>
void MinHeap<Type>::MakeEmpty()
{
    currentSize = 0;
}

template <class Type>
int MinHeap<Type>::Size()
{
    return currentSize;
}

6.9 最小重量机器设计问题

image-20220510155649875

解空间为深度为n的m叉树。

解空间树的第 i 层表示第 i 个物品，每一层有 m 个结点，分表表示对应的供应商，用数组 best_x[n] 表示最优解，其中 bestx[i] 表示第 i 个物品从第 bestx[i] 个供应商采购。

以当前扩展结点的重量作为优先级建立最小堆，从而实现活结点优先级队列。

当活结点队列不为空时，依次从中取出扩展结点，如果未到达叶结点，则遍历当前扩展结点的所有儿子结点（即遍历所有供应商）。

  • 如果儿子结点为叶结点，每次遍历供应商i时，判断当前解是否符合约束条件，以及是否为更优解，适当更新最优值与最优解。
  • 如果儿子结点不是叶结点，符合约束条件并又可能存在更优解，则将儿子结点加入到活结点优先级队列中。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
// 最小重量机器设计问题
#include <iostream>
#include <queue>
using namespace std;

// n个物品，m个供应商，最大价格d
const int maxn = 100;
int n, m, d;
int best_w = 0x3f3f3f; // 最优值，即最小重量
int best_x[maxn];      // 最优解，bestx[i]表示第i个物品从第bestx[i]个供应商采购
// c[i][j]第i个物品从第m个供应商采购的重量,w[i][j]为对应的价格
int c[maxn][maxn], w[maxn][maxn];

// 扩展结点
struct node
{
    // weight表示当前重量，cost表示当前话费，，source表示供应商
    // level表示层级，也表示第level个物品，其子结点为所有供应商
    // tmp_x存储当前最优解
    int weight, cost, level, source, tmp_x[maxn];
    node(int w, int c, int l, int s) : weight(w), cost(c), level(l), source(s) {}
    //小根堆, 返回true，则证明前者优先级低于后者
    bool operator<(const node &a) const
    {
        //若weigth>a.weigth为true，则a的优先级更高，即weigth小的对象优先级更高
        if (weight != a.weight)
            return weight < a.weight; 
        else if (level != a.level)
            return a.level < level;
        else
            return source > a.source;
    }
};

priority_queue<node> q;

int main()
{

    cin >> n >> m >> d;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            cin >> c[i][j];
        }
    }
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            cin >> w[i][j];
        }
    }
    // 初始化活结点优先级队列
    // 第一个物品选择哪一个供应商
    for (int i = 1; i <= m; i++)
    {
        node curr = node(w[1][i], c[1][i], 1, i);
        // 约束条件: 价格不超过d
        if (curr.cost <= d)
        {
            // 第一个物品选择第i个供应商
            curr.tmp_x[1] = i;
            // 加入活结点队列中
            q.push(curr);
        }
    }
    while (!q.empty())
    {
        // 取出当前扩展结点
        node curr = q.top();
        q.pop();
        if (curr.level < n) // 未到达叶结点
        {
            // 遍历当前扩展结点的所有子结点，即所有供应商
            for (int i = 1; i <= m; i++)
            {
                node curr_son = node(curr.weight + w[curr.level + 1][i], curr.cost + c[curr.level + 1][i], curr.level + 1, i);
                if (curr_son.level == n) // 如果扩展结点的子结点为叶结点
                {
                    // 最后一个物品选择供应商i
                    curr.tmp_x[curr_son.level] = i;
                    // 符合约束条件且得到更优值时，更新最优值与最优解
                    if (curr_son.weight < best_w && curr_son.cost <= d)
                    {
                        best_w = curr_son.weight;
                        for (int j = 1; j <= n; j++)
                            best_x[j] = curr.tmp_x[j];
                    }
                }
                else // 如果扩展结点的子结点不是叶结点
                {
                    if (curr_son.cost <= d && curr_son.weight < best_w)
                    {
                        // 前面的保持不变
                        for (int j = 1; j < curr_son.level; j++)
                        {
                            curr_son.tmp_x[j] = curr.tmp_x[j];
                        }
                        // 当前选择第i个供应商(儿子结点)加入到活结点队列中
                        curr_son.tmp_x[curr_son.level] = i;
                        q.push(curr_son);
                    }
                }
            }
        }
    }
    cout << best_w << endl;
    for (int i = 1; i <= n; i++)
    {
        cout << best_x[i] << " ";
    }
    cout << endl;
    return 0;
}