算法设计与分析实训课

矩阵连乘

  1. 动态规划表构建:
    1. dp[i][j] 表示从第i个矩阵到第j个矩阵的最小连乘次数。
    2. best_k[i][j] 记录了在计算dp[i][j]时选择的k值，即(i, k)和(k+1, j)是最佳分割点。
  2. 初始化:
    1. 对于所有长度为1的子序列（即单个矩阵），它们的连乘次数为0，因此dp[i][i]=0。
  3. 填充动态规划表:
    1. 使用双重循环遍历所有可能的矩阵链长度（len=2到n）。
    2. 对于每一个长度，再使用一个内层循环来确定当前考虑的矩阵链的起始位置i。
    3. 根据起始位置i和长度len确定结束位置j。
    4. 对于每一个(i, j)对，我们尝试所有的可能的分割点k，并计算分割后的两部分连乘所需的次数加上这两部分之间相乘的次数。
    5. 如果找到了更小的连乘次数，则更新dp[i][j]和best_k[i][j]。
  4. 结果输出:
    1. 最终，dp[1][n]中保存的就是从第一个矩阵到最后一个矩阵连乘的最小次数。
    2. printBestChain函数根据best_k记录的分割点信息递归地打印出最优的连乘路径。

给定矩阵序列$A_1,A_2,…,A_n$，其中每个矩阵$A_i$的尺寸大小为$p_{i-1} * p_i$，定义$dp[i][j]$为计算矩阵链$A_iA_{i+1}…A_j$所需的最小标量乘法次数，则动态规划推导公式为

$$dp[i][j] = \begin{cases} 0 & i = j, \ \min\limits_{i \leq k < j} (dp[i][k] + dp[k+1][j] + p_{i-1} \cdot p_k \cdot p_j) & i < j. \end{cases}$$

$k$为分割点

矩阵连乘

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
//By SnowDream
#include<bits/stdc++.h>
using namespace std;

// dp[i][j] 保存了从第 i 个矩阵到第 j 个矩阵之间最优解（即最小乘法次数）。
vector<vector<int>> dp;
// best_k[i][j] 记录了在计算 dp[i][j] 时选择的分割点 k，用于重建最优解路径。
vector<vector<int>> best_k;
// p 数组存储了每个矩阵的维度信息。p[i-1] 和 p[i] 分别是第 i 个矩阵的行数和列数。
vector<int> p;

// 矩阵链乘函数，n 是矩阵的数量。
void matrixChain(int n) {
    // 遍历所有可能的子链长度 len (2 到 n)，因为长度为 1 的子链不需要乘法。
    for(int len=2;len<=n;len++) {
        // 遍历所有可能的起始位置 i，结束位置 j = i + len - 1。
        for(int i=1;i+len-1<=n;i++) {
            int j = i+len-1;
            // 初始化 dp[i][j] 为 i 和 j 之间的直接乘法次数，并假设最佳分割点为 i。
            dp[i][j] = dp[i+1][j] + p[i-1] * p[i] * p[j];
            best_k[i][j]=i;
            // 尝试所有的分割点 k，寻找更小的乘法次数。
            for(int k=i+1;k<j;k++) {
                // 计算当前分割点 k 处的乘法次数。
                int tmp = dp[i][k] + dp[k+1][j] + p[i-1] * p[k] * p[j];
                // 如果找到了更小的乘法次数，更新 dp[i][j] 和最佳分割点 best_k[i][j]。
                if (tmp<dp[i][j]) {
                    dp[i][j] = tmp;
                    best_k[i][j] = k;
                }
            }
        }
    }
}

// 递归打印最优的矩阵链乘法顺序。
void printBestChain(int i, int j) {
    // 基本情况：当 i == j 时，表示只有一个矩阵，无需再分割。
    if(i==j)
        return;
    // 递归地打印左侧和右侧的子链。
    printBestChain(i,best_k[i][j]);
    printBestChain(best_k[i][j]+1,j);
    // 打印当前分割点处的乘法操作。
    cout << "A[" << i << ".." << best_k[i][j] << "] * A[" << best_k[i][j]+1 << ".." << j << "]\n";
}

// 主控制函数，处理用户输入和输出。
void snow() {
    int n;
    // 提示用户输入矩阵的数量。
    cout << "请输入矩阵个数:" << flush;
    cin >> n;
    // 初始化 p, dp, best_k 向量。
    p = vector<int>(n+1,0);
    dp = vector<vector<int>>(n+1,vector<int>(n+1,0));
    best_k = vector<vector<int>>(n+1,vector<int>(n+1,0));
    // 提示用户输入矩阵的维度。
    cout << "请输入矩阵:" << flush;
    for(int i=0;i<=n;i++) {
        cin >> p[i]; // 输入的是矩阵链中相邻两个矩阵相乘时的维度，包括最外层的维度。
    }
    // 调用 matrixChain 函数计算最小连乘次数。
    matrixChain(n);
    // 输出最小连乘次数和最优连乘路径。
    cout << "最小连乘次数: " << dp[1][n] << "\n最优连乘路径为: \n";
    printBestChain(1,n);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    snow();
    return 0;
}

奖学金问题

使用贪心算法，将课程的成绩按照每提高一分所需要的时间从小到大排序，优先学习消耗时间小的

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
#include<bits/stdc++.h>
using namespace std;

// 定义一个结构体来存储每个课程的成绩的两个部分：平时成绩 和 所需要的时间。
struct score {
    double a; //平时成绩。
    double b; //每提高一分所需要的时间。
};

// 比较函数，用于对成绩按照 b 的值进行排序。
bool cmp(score x, score y) {
    return x.b < y.b;
}

void snow() {
    int n;
    // 读取输入直到遇到 n=0 的情况。
    while (cin >> n) {
        if(n==0)
            break;
        int ans = 0; // 最少复习时间
        double sum = 0, avg, max_score; // sum 平时成绩之和，avg 目标平均分，max_score 最大单科成绩。
        vector<score> scores(n); // 创建一个大小为 n 的向量来存储成绩。

        // 读取 n 个成绩，并将它们的 a 部分（即平时成绩）相加到 sum 中。
        for (int i = 0; i < n; i++) {
            cin >> scores[i].a >> scores[i].b;
            sum += scores[i].a;
        }

        // 读取最大成绩 max_score 和目标平均分 avg。
        cin >> max_score >> avg;

        // 计算为了达到目标平均分还需要多少分数。
        double need_score = avg * n - sum;

        // 如果还未到达目标分数
        if (need_score > 0) {
            // 根据获取或提升每一分的成本 b 对成绩进行升序排序。
            sort(scores.begin(), scores.end(), cmp);

            // 尝试通过提高成绩来获得所需的分数。
            for (int i = 0; i < n; i++) {
                // 计算可以提高的最大分数 tmp。
                double tmp = max_score - scores[i].a;

                // 如果剩余需要的分数大于可以通过当前成绩提高的最大分数，则全部使用。
                if(need_score - tmp > 0) {
                    need_score -= tmp;
                    ans += int(tmp * scores[i].b); // 累加成本。
                } else {
                    // 否则，只需要增加足够的分数以满足需求。
                    ans += int(need_score * scores[i].b);
                    break; // 达到目标后退出循环。
                }
            }
        }
        // 输出总成本
        cout << ans << "\n";
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    snow();
    return 0;
}

布线问题分支限界法

这段代码实现了分支限界法（Branch and Bound）来寻找一个从起点到终点的最短路径。这个算法适用于在一个有障碍物的网格中找到一条没有障碍且成本最小的路径。

  1. 结构体定义:

    1. Node 结构体用来表示网格中的一个节点，它包含了节点的坐标 (x, y) 以及到达该节点的累计成本 cost。
    2. 重载了 < 运算符，使得我们可以使用 C++ 的 priority_queue 来创建一个最小堆，从而总是优先处理成本最低的节点。

  2. 辅助函数:

    1. check(int x, int y)：检查给定的坐标是否在矩阵的有效范围内。
    2. print_path(const vector<Node> &path)：用于打印出找到的最佳路径。

  3. 核心算法:

    1. branch_and_bound(vector<vector<int>> matrix, Node start, Node target, vector<Node> &best_path)：
      • 使用 priority_queue<Node> 来存储待处理的节点，并按照 cost 从小到大排序。
      • visited 矩阵用于记录哪些节点已经被访问过，以避免重复访问。
      • parent 矩阵用于追踪每个节点的父节点，这样可以在找到目标节点后回溯构建完整路径。
      • min_cost 变量保存当前找到的最小路径成本，初始值为 INT_MAX。
      • 初始化时将起点加入优先队列，并标记为已访问。
      • 在循环中，每次取出成本最小的节点进行处理，如果它是目标节点，则更新最佳路径。
      • 尝试向四个方向移动（上下左右），对于每一个新位置，如果它在有效范围内、未被访问且不是障碍，则计算其成本并将其加入队列。
      • 如果新路径的成本已经超过已知的最小成本，则跳过这条路径（剪枝）。

  4. 测试用例:

    1. snow() 函数初始化了一个 7x7 的邻接矩阵 matrix，其中 0 表示可通行，1 表示障碍。
    2. 定义了起始点 start 和目标点 target。
    3. 调用了 branch_and_bound 函数来寻找从 start 到 target 的最佳路径。
    4. 最后输出了邻接矩阵和找到的最佳路径。

在分支限界法中，剪枝策略是通过设定界限来排除不可能包含最优解的分支，从而减少搜索空间，提高算法效率。对于左剪枝和右剪枝的理解，通常与二叉树结构相关联，但在更一般的解空间树（如排列树或子集树）中，剪枝的概念同样适用。我们可以将“左剪枝”和“右剪枝”理解为对当前节点的不同选择路径进行剪枝。

1. 确定界限

要实现有效的剪枝，首先需要确定一个合适的界限。这个界限可以是：

  • 上界 (Upper Bound)：对于最大化问题，上界是任何可行解的目标函数值的最大可能值。
  • 下界 (Lower Bound)：对于最小化问题，下界是任何可行解的目标函数值的最小可能值。

这些界限可以帮助你判断当前分支是否有可能产生比已知最佳解更好的解。

2. 左剪枝和右剪枝的定义

在回溯法或分支限界法中，“左剪枝”和“右剪枝”并不是固定的术语，而是指根据某种规则或条件，决定是否继续探索某个分支。具体来说：

  • 左剪枝：通常指的是放弃当前节点的左侧子树（即选择当前元素的情况）。例如，在子集树中，左剪枝意味着不选择当前元素。
  • 右剪枝：通常指的是放弃当前节点的右侧子树（即不选择当前元素的情况）。例如，在子集树中，右剪枝意味着选择当前元素。

然而，在更一般的情况下，剪枝是指放弃任何不符合界限条件的分支。因此，我们可以通过以下方式来确定何时进行剪枝：

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
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
//By SnowDream
#include <bits/stdc++.h>
using namespace std;

const int n = 7; // 矩阵行数
const int m = 7; // 矩阵列数

// 结点结构体定义
struct Node {
    int x, y;
    int cost; // 到达该结点的累计成本

    Node(int x = 0, int y = 0, int cost = 0) : x(x), y(y), cost(cost) {}

    // 重载小于运算符，使得priority_queue按最小堆排列
    bool operator<(const Node& other) const {
        return cost > other.cost; // 最小堆
    }
};

// 检查是否在范围内
bool check(int x, int y) {
    return x >= 0 && x < n && y >= 0 && y < m;
}

// 打印路径
void print_path(const vector<Node> &path) {
    for (auto it: path) {
        cout << "(" << it.x << ", " << it.y << ") ";
    }
    cout << "\n";
}

// 使用优先级队列实现分支限界法
void branch_and_bound(vector<vector<int>> matrix, Node start, Node target, vector<Node> &best_path) {
    priority_queue<Node> pq; // 存储待处理的节点
    vector<vector<int>> min_cost(n, vector<int>(m, INT_MAX)); // 记录到达每个节点的最小成本
    vector<vector<Node>> parent(n, vector<Node>(m, Node(-1, -1))); // 记录每个节点的父节点
    best_path.clear();
    int final_cost = INT_MAX; // 当前找到的最小成本

    // 初始化起点
    pq.push(start);
    min_cost[start.x][start.y] = 0;

    while (!pq.empty()) {
        Node current = pq.top();
        pq.pop();

        // 如果到达目标结点
        if (current.x == target.x && current.y == target.y) {
            // 更新最佳路径
            if (current.cost < final_cost) {
                final_cost = current.cost;
                best_path.clear();
                for (Node p = current; p.x != -1 && p.y != -1; p = parent[p.x][p.y]) {
                    best_path.push_back(p);
                }
                reverse(best_path.begin(), best_path.end());
            }
            continue; // 不需要继续扩展这个节点
        }

        // 尝试向四个方向移动：上、下、左、右
        int dx[] = {0, 0, -1, 1};
        int dy[] = {-1, 1, 0, 0};

        for (int i = 0; i < 4; ++i) {
            int new_x = current.x + dx[i];
            int new_y = current.y + dy[i];

            if (check(new_x, new_y) && matrix[new_x][new_y] == 0) {
                // 计算新路径的成本
                int new_cost = current.cost + 1;

                // 剪枝：如果新路径的成本已经超过已知的最小成本，则不再考虑这条路径
                if (new_cost >= final_cost) {
                    continue;
                }

                // 如果新路径的成本比之前到达该节点的成本更低，则更新
                if (new_cost < min_cost[new_x][new_y]) {
                    min_cost[new_x][new_y] = new_cost;
                    parent[new_x][new_y] = current;
                    Node next_node(new_x, new_y, new_cost); // 假设每次移动成本为1
                    pq.push(next_node);
                }
            }
        }
    }
}

void snow() {
    // 创建一个n x m的邻接矩阵，0表示可以走，1表示障碍
    vector<vector<int>> matrix(n, vector<int>(m, 0));

    // 添加一些障碍
    matrix[0][2] = 1;
    matrix[0][3] = 1;
    matrix[1][3] = 1;
    matrix[2][4] = 1;
    matrix[3][3] = 1;
    matrix[3][4] = 1;
    matrix[4][0] = 1;
    matrix[4][4] = 1;
    matrix[5][0] = 1;
    matrix[5][1] = 1;
    matrix[5][2] = 1;
    matrix[6][0] = 1;
    matrix[6][1] = 1;
    matrix[6][2] = 1;

    // 打印邻接矩阵
    cout << "邻接矩阵:\n";
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            cout << matrix[i][j] << " ";
        }
        cout << "\n";
    }

    // 定义起始和目标结点
    Node start(2, 1, 0); // 起点成本为0
    Node target(3, 5);

    // 存储最佳路径
    vector<Node> best_path;

    // 执行分支限界法
    branch_and_bound(matrix, start, target, best_path);

    // 输出结果
    if (!best_path.empty()) {
        cout << "找到的最佳路径: ";
        print_path(best_path);
        cout << "最小成本: " << best_path.back().cost << "\n";
    } else {
        cout << "无法找到从起点到终点的路径。\n";
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    snow();
    return 0;
}

密码问题

这个问题属于组合优化问题，因为它要求从给定的字符串中选择一组元素（即5个字母），并且这些元素需要满足一个特定的数学条件。此外，由于你需要找到字典序最大的解，这也引入了对排列顺序的要求。

分析步骤

  1. 理解问题约束和目标
    1. 你有一个整数 n 和一个由不同大写字母组成的字符串 str。
    2. 每个字母对应一个序数（A=1, B=2, …, Z=26）。
    3. 你需要从 str 中选出5个不同的字母，构成一个密码，使得这5个字母的序数按照特定公式计算的结果等于 n。
    4. 如果有多个解，你需要返回字典序最大的那个解。
  2. 确定解空间树类型
    1. 因为你要从 str 中选择5个字母，所以这是一个排列生成问题。这意味着解空间树应该是一个排列树，因为每个位置上的字母不能重复，并且顺序会影响最终的结果。
  3. 设计算法
    1. 你可以使用回溯法来遍历所有可能的5个字母的排列，并检查它们是否满足给定的等式。
    2. 在遍历过程中，一旦找到满足条件的解，就将其保存下来。由于你需要字典序最大的解，因此每当找到一个新的满足条件的解时，你应该与当前保存的最佳解进行比较，保留字典序更大的那一个。

选择使用子集树还是排列树进行回溯，主要取决于问题的具体要求和解空间的性质。以下是帮助你判断应该使用哪种类型的解空间树的一些指导原则：

1. 子集树 (Subset Tree)

适用场景：

  • 元素的选择性：如果你需要从一组元素中选择一个或多个元素组成解，而这些元素之间的顺序不重要，那么你应该使用子集树。
  • 二元选择：在每个决策点上，你只有两种选择：选或不选当前元素。例如，0-1背包问题就是一个典型的子集树问题，因为对于每个物品，你只有两种选择：放入背包或不放入。

例子：

  • 0-1背包问题：给定一组物品，每个物品有一个重量和价值，在不超过总重量限制的情况下，选择一些物品使得总价值最大。
  • 子集和问题：给定一个整数集合，找出所有可能的子集，使得这些子集的元素之和等于给定的目标值。

特点：

  • 子集树的每个节点有两个子节点，表示选择当前元素与否。
  • 树的深度等于元素的数量。
  • 每个叶节点代表一个可能的解（即一个元素的子集）。

2. 排列树 (Permutation Tree)

适用场景：

  • 元素的排列：如果你需要从一组元素中选择若干个元素，并且这些元素的顺序对解有影响，那么你应该使用排列树。
  • 全排列：在每个决策点上，你需要选择一个未被选择过的元素加入当前部分解中，直到所有元素都被选择过。例如，旅行商问题（TSP）就是一个典型的排列树问题，因为路径中的城市顺序非常重要。

例子：

  • **旅行商问题(TSP)**：给定一组城市及其两两之间的距离，找到一条经过每个城市恰好一次并返回起点的最短路径。
  • N皇后问题：在一个N×N的棋盘上放置N个皇后，使得它们互不攻击，即任意两个皇后不在同一行、同一列或同一对角线上。

特点：

  • 排列树的每个节点的子节点数会随着层数增加而减少，因为每向下一层，可用的选择就会减少一个。
  • 树的深度等于需要排列的元素数量。
  • 每个叶节点代表一个可能的解（即一个元素的排列）。

3. 如何选择

  • 考虑顺序的重要性：
    • 如果元素的顺序不影响解，则使用子集树。
    • 如果元素的顺序对解有影响，则使用排列树。
  • 考虑选择的方式：
    • 如果每次选择是二元的（选或不选），则使用子集树。
    • 如果每次选择是从剩余元素中选取一个，则使用排列树。
  • 考虑解的空间大小：
    • 子集树的解空间大小为 $2^n$，其中 $n$ 是元素的数量。
    • 排列树的解空间大小为 $n!$，其中 $n$ 是元素的数量。

4. 具体到你的问题

对于你提到的问题（从字符串中选择5个字母构成密码，并满足特定条件），由于：

  • 顺序对结果有影响：因为公式 v - w^2 + x^3 - y^4 + z^5 中字母的位置不同会导致不同的计算结果。
  • 需要选择5个不同的字母：每次选择都是从剩余的字母中选取一个。

因此，这个问题更适合使用排列树来解决。排列树能够确保你探索所有可能的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
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
//By SnowDream
#include <bits/stdc++.h>
using namespace std;

// 计算函数
int calculate(int v, int w, int x, int y, int z) {
    return v - w * w + x * x * x - y * y * y * y + z * z * z * z * z;
}

// 回溯函数
void backtrack(vector<int>& nums, vector<int>& current, string& ans_str, int n, int start) {
    // 如果当前组合长度为5，检查是否满足条件
    if (current.size() == 5) {
        if (calculate(current[0], current[1], current[2], current[3], current[4]) == n) {
            string tmp_str;
            for (int num : current) {
                tmp_str += 'A' + num - 1;
            }
            // 更新最大字典序的密码
            if (ans_str.empty() || tmp_str > ans_str) {
                ans_str = tmp_str;
            }
        }
        return;
    }

    // 尝试添加新的字母到当前组合
    for (int i = start; i < nums.size(); ++i) {
        // 交换元素以生成不同的排列
        swap(nums[i], nums[start]);
        current.push_back(nums[start]);
        // 继续递归搜索
        backtrack(nums, current, ans_str, n, start + 1);
        // 恢复现场（撤销选择）
        current.pop_back();
        swap(nums[i], nums[start]);
    }
}

string find_max_str(int n, const string& str) {
    // 将字符串转换为对应的序数列表
    vector<int> nums;
    for (char c : str) {
        nums.push_back(c - 'A' + 1);
    }

    // 对序数列表进行排序，以便从大到小尝试
    sort(nums.begin(), nums.end(), greater<>());

    // 初始化最大密码
    string ans_str;

    // 使用回溯法寻找最佳解
    vector<int> current;
    backtrack(nums, current, ans_str, n, 0);

    return ans_str;
}

void snow() {
    while (true) {
        int n;
        string str;

        cin >> n;
        if (n == 0) {
            break;
        }

        cin >> str;

        string result = find_max_str(n, str);
        if (!result.empty()) {
            cout << result << endl;
        } else {
            cout << "no solution" << endl;
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    snow();
    return 0;
}

幂集和全排列

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
//By SnowDream
#include <bits/stdc++.h>
using namespace std;

typedef vector<vector<int>> vvi;

vvi pset(int n) {
    if(n==0) return {{}};
    vvi ps;
    ps = pset(n-1);
    int m = (int)ps.size();
    for(int i=0;i<m;i++) {
        auto e = ps[i];
        e.push_back(n);
        ps.push_back(e);
    }
    return ps;
}

vvi perm(int n) {
    vvi ps;
    vector<int> e;
    for (int i = 1; i <= n ; ++i) {
        e.push_back(i);
    }
    do {
        ps.push_back(e);
    } while (next_permutation(e.begin(), e.end()));
    return ps;
}

void print(const vvi &ans) {
    for(auto i:ans) {
        cout << "{";
        for(auto j:i){
            cout << j << ", ";
        }
        cout << "}, ";
    }
}

void snow() {
    int n=4;
    vvi ans_pset = pset(n);
    cout << n << "的幂集为\n";
    print(ans_pset);
    cout << "\n";
    vvi ans_perm = perm(n);
    cout << n << "的全排列为\n";
    print(ans_perm);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    snow();
    return 0;
}

01背包问题

穷举法

时间复杂度：$O(2^n)$

穷举法会生成并检查所有可能的物品组合。对于n个物品，每个物品都有两种状态（选中或不选），因此总共有$2^n$种可能的组合。在最坏的情况下，它需要遍历所有的这些组合来找到最优解。这意味着穷举法的时间复杂度是指数级的，随着物品数量的增长，计算量将急剧增加，适用于非常小规模的问题。

回溯法

时间复杂度：最好情况为$O(n)$，最坏情况为$O(2^n)$

回溯法通过使用边界函数来估计剩余物品可能达到的最大价值，并以此决定是否继续搜索当前路径。如果能够有效地剪枝，即提前排除不可能产生更优解的分支，那么回溯法可以在某些情况下显著减少搜索空间。

在最好的情况下，如果剪枝非常有效，那么只需要探索很少的分支就能找到最优解，此时的时间复杂度接近于线性$O(n)$。

在最坏的情况下，当没有有效的剪枝时，回溯法仍然需要探索几乎所有的可能性，其时间复杂度接近于$O(2^n)$。

动态规划

时间复杂度：$O(n*W)$

动态规划通过构建一个二维数组dp，其中dp[i][w]表示前i个物品在总重量不超过w的情况下的最大价值。为了填充这个表，算法需要对每个物品和每个可能的重量进行一次操作。因此，总的计算次数为物品的数量n乘以背包的最大承重W。所以，动态规划的时间复杂度为$O(n*W)$。这种线性时间复杂度使得动态规划非常适合处理较大规模的问题，只要W不是特别大。

总结

  • 穷举法的时间复杂度是$O(2^n)$，适合极小规模的问题，因为它的计算量随物品数量呈指数增长。
  • 回溯法的时间复杂度在最坏情况下也是$O(2^n)$，但在实际应用中，由于剪枝的存在，通常会比穷举法更快。其性能依赖于剪枝的有效性，最好情况下可以达到$O(n$。
  • 动态规划提供了一个确定的时间复杂度$O(n*W)$，它避免了重复计算子问题，适用于大多数实际场景，特别是当物品数量较多且背包容量适中时。

穷举法

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
//By SnowDream
#include <bits/stdc++.h>
using namespace std;

void print(vector<bool> selected_items, vector<int> weights, vector<int> values) {
    int total_weight = 0, total_value = 0;

    cout << "{";
    for (size_t i = 0; i < selected_items.size(); ++i) {
        if (selected_items[i]) {
            cout << i << ", ";
            total_weight += weights[i];
            total_value += values[i];
        }
    }
    cout << "}\n" << "总重量为: " << total_weight << "，总价值为: " << total_value;
}

void knap(vector<int> weights, vector<int> values, int max_weight, vector<bool>& best_selected) {
    int n = weights.size();
    int max_v = 0;

    // 遍历所有可能的物品组合
    for (int combination = 0; combination < (1 << n); ++combination) {
        vector<bool> selected(n, false);

        // 检查当前组合中的每个物品
        int sum_w = 0, sum_v = 0;
        for (int i = 0; i < n; ++i) {
            if (combination & (1 << i)) { // 如果物品i被选中
                selected[i] = true;
                sum_w += weights[i];
                sum_v += values[i];
            }
        }

        // 如果当前组合的总重量不超过最大限制且总价值更大，则更新最优解
        if (sum_w <= max_weight && sum_v > max_v) {
            max_v = sum_v;
            best_selected = selected; // 更新最优选择
        }
    }
}

void snow() {
    vector<int> weights = {5, 3, 2, 1}; // 物品的重量
    vector<int> values = {4, 4, 3, 1};  // 物品的价值
    int max_weight = 6;                 // 背包的最大承重
    vector<bool> best_selected;         // 用来存储最优解的物品选择状态
    knap(weights, values, max_weight, best_selected);
    print(best_selected, weights, values);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    snow();
    return 0;
}

回溯法

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
// By SnowDream
#include <bits/stdc++.h>
using namespace std;

// 定义商品结构体，包含编号、重量和价值
struct Good {
    int no; // 商品编号
    int weight;  // 商品重量
    int value;  // 商品价值
    // 构造函数初始化商品信息
    Good(int no, int w, int v) : no(no), weight(w), value(v) {}

    // 重载小于运算符，用于排序，按照单位重量的价值从高到低排序
    bool operator<(const Good &s) const {
        return (double)value / weight > (double)s.value / s.weight;
    }
};

int max_weight; // 背包最大承重
int n;      // 商品数量
vector<int> selected;          // 当前解向量，表示每个商品是否被选中（1为选中，0为未选中）
vector<int> best_selected;      // 最佳解向量
int best_value = 0;          // 最佳解的总价值
int tot = 0;            // 搜索次数计数器
vector<Good> g;         // 存储所有商品信息的向量

void print() {
    int current_weight = 0;
    cout << "{";
    for (int i = 0; i < n; i++) {
        if (best_selected[i] == 1) {
            cout << g[i].no << ", ";
            current_weight += g[i].weight;
        }
    }
    cout << "}\n总重量为: " << current_weight << "，总价值为: " << best_value;
}

// 计算边界函数，用于估计剩余物品可能达到的最大价值
double bound(int cw, int cv, int i) {
    int rw = max_weight - cw; // 剩余可承载重量
    double b = cv;        // 当前估计的总价值
    int j = i;
    // 尽可能多地选择剩余物品，直到不能再装下整个物品为止
    while (j < n && g[j].weight <= rw) {
        rw -= g[j].weight;
        b += g[j].value;
        j++;
    }
    // 如果还有剩余空间，则按最后一个能部分装入的物品的单位重量价值填充
    if (j < n) {
        b += (double)g[j].value / g[j].weight * rw;
    }
    return b;
}

void dfs(int current_weight, int current_value, int i) {
    tot++; // 每进入一次递归调用，增加搜索次数计数
    // 如果已经遍历完所有商品
    if (i >= n) {
        // 如果当前解的总重量不超过背包容量且总价值大于最佳解，则更新最佳解
        if (current_weight <= max_weight && current_value > best_value) {
            best_value = current_value;
            best_selected = selected;
        }
    } else {
        // 尝试选择第i个商品
        if (current_weight + g[i].weight <= max_weight) {
            selected[i] = 1; // 标记第i个商品被选中
            dfs(current_weight + g[i].weight, current_value + g[i].value, i + 1); // 递归搜索下一个商品
        }
        // 计算不选择第i个商品时的上界
        double b = bound(current_weight, current_value, i + 1);
        // 如果上界仍然大于当前最佳解的价值，继续搜索
        if (b > best_value) {
            selected[i] = 0; // 标记第i个商品不被选中
            dfs(current_weight, current_value, i + 1); // 递归搜索下一个商品
        }
    }
}

void snow() {
    g = {Good(0, 5, 4), Good(1, 3, 4), Good(2, 2, 3), Good(3, 1, 1)};
    max_weight = 6;
    n = g.size();
    sort(g.begin(), g.end());
    selected = vector<int>(n, 0);
    dfs(0, 0, 0);
    print();
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    snow();
    return 0;
}

动态规划

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
//By SnowDream
#include <bits/stdc++.h>
using namespace std;

vector<vector<int>> dp;

void knap(vector<int> weights, vector<int> values, int max_weight) {
    int n = weights.size();
    dp = vector<vector<int>>(n + 1, vector<int>(max_weight + 1, 0));
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= max_weight; j++) {
            if (j < weights[i - 1]) {
                dp[i][j] = dp[i - 1][j];
            } else {
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weights[i - 1]] + values[i - 1]);
            }
        }
    }
}

void print(vector<int> weights, int max_weight) {
    int n = weights.size();
    vector<int> res(n, 0);
    int i = n, j = max_weight, current_weight = 0;
    while (i > 0 && j > 0) {
        if (dp[i][j] != dp[i - 1][j]) {
            res[i - 1] = 1;
            current_weight += weights[i - 1];
            j -= weights[i - 1];
        }
        i--;
    }
    cout << "{";
    for (int k = 0; k < n; k++) {
        if (res[k])
            cout << k << ", ";
    }
    cout << "}\n总重量为: " << current_weight << "，总价值为: " << dp[n][max_weight];
}

void snow() {
    vector<int> weights = {5, 3, 2, 1};
    vector<int> values = {4, 4, 3, 1};
    int max_weight = 6;
    knap(weights, values, max_weight);
    print(weights, max_weight);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    snow();
    return 0;
}
#算法设计与分析
算法设计与分析实训课
http://snowdreamxue.github.io/2025/01/08/算法分析实训课/
Author
SnowDream
Posted on
January 8, 2025
Licensed under