大学选课问题：动态规划、贪心和分支限界算法的应用

问题描述： 在一所大学中，有多个课程可以选择，每个学生可以选择多门课程，但每门课程只能容纳一定数量的学生，且每个学生对于每门课程都有一个对应的成绩。如何安排每个学生选课，使得每门课程的容量限制不超过，并使得所有学生选的课程总成绩最高。

算法选择：

**动态规划法：**将每个学生选的课程和对应成绩看作一个物品，将每门课程看作一个背包，使用动态规划算法求解。时间复杂度为O(nm)，n为学生数量，m为课程数量。
**贪心法：**对于每门课程，按照学生的成绩从高到低排序，依次将学生加入课程，直到课程容量限制达到。时间复杂度为O(mnlogn)，n为学生数量，m为课程数量。
**分支限界法：**将每个学生选的课程和对应成绩看作一个节点，每个节点有两个分支，分别表示选或不选该课程。对于每个节点，计算当前已选课程的总成绩，并估计剩下未选课程的最大成绩。根据估价函数对节点进行排序，优先扩展估价函数更高的节点。时间复杂度取决于估价函数的计算复杂度。

算法实现：

动态规划法：

用一个二维数组dp[i][j]表示前i个学生选前j门课程的最大总成绩。
初始化dp[0][j]=0，dp[i][0]=0。
对于每个学生i和每门课程j，如果该学生选了该课程，则dp[i][j]=dp[i-1][j-1]+score[i][j]；如果该学生没选该课程，则dp[i][j]=dp[i-1][j]。
最终答案为dp[n][m]，其中n为学生数量，m为课程数量。

int dp[N][M]; // N为学生数量，M为课程数量
int score[N][M]; // 学生成绩
int capacity[M]; // 课程容量

int dynamic_programming() {
    for (int i = 0; i <= N; i++) {
        dp[i][0] = 0;
    }
    for (int j = 0; j <= M; j++) {
        dp[0][j] = 0;
    }
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= M; j++) {
            if (capacity[j] > 0) {
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1] + score[i][j]);
                capacity[j]--;
            } else {
                dp[i][j] = dp[i - 1][j];
            }
        }
    }
    return dp[N][M];
}

贪心法：

对每门课程按照学生成绩从高到低排序。
对于每门课程，依次将学生加入课程，直到课程容量限制达到。

int greedy_algorithm() {
    int total_score = 0;
    for (int j = 0; j < M; j++) {
        vector<pair<int, int>> students; // 学生成绩和序号
        for (int i = 0; i < N; i++) {
            students.push_back(make_pair(score[i][j], i));
        }
        sort(students.begin(), students.end(), greater<pair<int, int>>());
        int count = 0;
        for (auto student : students) {
            if (count < capacity[j]) {
                total_score += student.first;
                count++;
            } else {
                break;
            }
        }
    }
    return total_score;
}

分支限界法：

将每个学生选的课程和对应成绩看作一个节点，初始化一个空的集合S。
计算S中已选课程的总成绩sum，并估计剩下未选课程的最大成绩max。
如果max+sum小于当前最优解，则剪枝。
对于每门未选课程，创建两个节点，分别表示选或不选该课程，计算新集合的sum和max，并将节点插入优先队列中。
从优先队列中取出估价函数最高的节点进行扩展，直到队列为空或已找到最优解。

struct Node {
    int sum; // 当前总成绩
    int max; // 估计最大成绩
    vector<int> courses; // 已选课程
    // 比较函数，优先扩展估计最大成绩更高的节点
    bool operator<(const Node& other) const {
        return max < other.max;
    }
};

int branch_and_bound() {
    priority_queue<Node> pq;
    Node start = {0, 0, {}};
    pq.push(start);
    int best_score = 0;
    while (!pq.empty()) {
        Node cur = pq.top();
        pq.pop();
        if (cur.sum + cur.max < best_score) { // 剪枝
            continue;
        }
        if (cur.courses.size() == M) { // 所有课程都已选
            best_score = max(best_score, cur.sum);
            continue;
        }
        // 扩展节点
        for (int j = 0; j < M; j++) {
            if (find(cur.courses.begin(), cur.courses.end(), j) == cur.courses.end()) { // 未选课程
                vector<int> new_courses = cur.courses;
                new_courses.push_back(j);
                int new_sum = cur.sum + score[cur.courses.size()][j];
                int new_max = cur.max; // 估计最大成绩
                Node new_node = {new_sum, new_max, new_courses};
                pq.push(new_node);
            }
        }
    }
    return best_score;
}

未使用的三种算法：

**蛮力法：**枚举所有选课方案，计算每个方案的总成绩，找到最优解。时间复杂度为O(2^n)，n为课程数量，无法处理大规模问题。
**回溯法：**类似于分支限界法，不同之处在于回溯法并不会对节点进行排序，而是依次扩展所有节点。时间复杂度取决于搜索树的大小，通常比分支限界法慢。
**分治法：**将所有学生分成两组，分别解决左右两组的选课问题，将两组的解合并得到最终解。时间复杂度取决于分组的方式，通常比贪心法和动态规划法慢。

原因：

蛮力法时间复杂度过高，不适合解决大规模问题。
回溯法没有利用估价函数进行剪枝，效率低于分支限界法。
分治法在该问题中没有明显的优势，时间复杂度可能高于动态规划法或贪心法。

测试数据设计：

为了测试算法的正确性和效率，可以设计以下测试数据：

**小规模数据：**学生数量和课程数量较少，方便手动验证结果。
**大规模数据：**学生数量和课程数量较多，测试算法的效率和稳定性。
**特殊数据：**例如，所有学生的成绩都相同，或所有课程的容量都相同，测试算法在特殊情况下的表现。

总结：

本文介绍了三种解决大学选课问题的算法：动态规划法、贪心法和分支限界法。动态规划法具有较高的效率，但需要较大的空间复杂度；贪心法相对简单，但可能无法找到最优解；分支限界法可以找到最优解，但效率取决于估价函数的质量。在实际应用中，需要根据问题的规模和对解的精度要求选择合适的算法。