当前位置：首页 > 其他 > 1997年CTSC选课问题（洛谷P2014）解题全解析：动态规划与树形结构实战

1997年CTSC选课问题（洛谷P2014）解题全解析：动态规划与树形结构实战

4个月前 (07-04)

一、题目解读

CTSC选课问题（洛谷P2014）要求在一个具有依赖关系的课程树中，选择m门课程以获得最大总学分。课程之间存在先修关系，即某些课程必须在其前置课程被选修后才能选择。题目核心在于如何高效处理依赖关系并求解最优组合，属于典型的动态规划应用场景。

二、解题思路

采用动态规划+树形结构求解：

1. 树形结构建模：使用vector构建课程树，每门课程作为节点存储其子节点（后续课程）。

2. 虚拟根节点：添加节点0作为虚拟根，将所有无前置课程的节点挂在其下，确保DP从单一入口开始。

3. 动态规划状态定义：dp[u][m]表示以u为根节点选m门课的最大学分。

4. 分组背包优化：对每个子树进行分组背包DP，倒序枚举避免重复计算，确保每门课仅被选一次。

5. 关键逻辑：必须选修当前课程才能选其子课程（虚拟根除外），通过逆向更新实现。

三、解题步骤

1. 输入与构建课程树：读入n门课程，每门课程的前置节点pre与学分credit，将课程i加入pre的子节点列表。

2. 虚拟根初始化：节点0作为根，所有无前置课程的节点挂在其下。

3. 深度优先搜索（DFS）：从根节点0开始递归，遍历每个子树：

递归处理子节点v，更新v的子树dp值。

对当前节点u：

倒序枚举m门课的组合，通过分组背包合并子树v的最优解。

若u非虚拟根，强制选择u后更新剩余学分组合的dp值。

4. 输出结果：最终答案存储在dp[0][m]，即从虚拟根选m门课的最大学分。

四、代码与注释

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

const int MAXN = 310;
vector<int> tree[MAXN];  // 课程树结构
int credit[MAXN];        // 课程学分
int dp[MAXN][MAXN];      // dp[u][m]表示以u为根选m门课的最大学分
int n, m;

// 深度优先搜索+动态规划
void dfs(int u) {
    for(int v : tree[u]) {  // 遍历所有子节点
        dfs(v);
        // 分组背包过程（倒序枚举）
        for(int j = m; j >= 0; j--) {
            for(int k = 1; k <= j; k++) {
                dp[u][j] = max(dp[u][j], dp[u][j-k] + dp[v][k]);  // 合并子树最优解
            }
        }
    }
    // 必须选当前课程才能选其子课程（虚拟根0除外）
    if(u!= 0) {
        for(int j = m; j >= 1; j--) {
            dp[u][j] = dp[u][j-1] + credit[u];  // 强制选u后更新学分
        }
    }
}

int main() {
    cin >> n >> m;  // 课程数n，需选m门
    // 构建课程树，0为虚拟根节点
    for(int i = 1; i <= n; i++) {
        int pre;
        cin >> pre >> credit[i];
        tree[pre].push_back(i);  // 前置课程pre的子节点为i
    }
    
    dfs(0);  // 从虚拟根开始DP
    cout << dp[0][m] << endl;  // 输出最优学分
    return 0;
}