1997年CTSC选课问题解题：动态规划与树形结构实战

19339201706

一、题目解读

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

二、解题思路

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

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

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

3. 动态规划状态定义：dp[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门课的最大学分。

四、代码与注释

1. #include <iostream>
   
2. #include <vector>
   
3. #include <algorithm>
   
4. using namespace std;
   
5. 
   
6. const int MAXN = 310;
   
7. vector<int> tree[MAXN];  // 课程树结构
   
8. int credit[MAXN];        // 课程学分
   
9. int dp[MAXN][MAXN];      // dp[u][m]表示以u为根选m门课的最大学分
   
10. int n, m;
    
11. 
    
12. // 深度优先搜索+动态规划
    
13. void dfs(int u) {
    
14.     for(int v : tree[u]) {  // 遍历所有子节点
    
15.         dfs(v);
    
16.         // 分组背包过程（倒序枚举）
    
17.         for(int j = m; j >= 0; j--) {
    
18.             for(int k = 1; k <= j; k++) {
    
19.                 dp[u][j] = max(dp[u][j], dp[u][j-k] + dp[v][k]);  // 合并子树最优解
    
20.             }
    
21.         }
    
22.     }
    
23.     // 必须选当前课程才能选其子课程（虚拟根0除外）
    
24.     if(u!= 0) {
    
25.         for(int j = m; j >= 1; j--) {
    
26.             dp[u][j] = dp[u][j-1] + credit[u];  // 强制选u后更新学分
    
27.         }
    
28.     }
    
29. }
    
30. 
    
31. int main() {
    
32.     cin >> n >> m;  // 课程数n，需选m门
    
33.     // 构建课程树，0为虚拟根节点
    
34.     for(int i = 1; i <= n; i++) {
    
35.         int pre;
    
36.         cin >> pre >> credit[i];
    
37.         tree[pre].push_back(i);  // 前置课程pre的子节点为i
    
38.     }
    
39.    
    
40.     dfs(0);  // 从虚拟根开始DP
    
41.     cout << dp[0][m] << endl;  // 输出最优学分
    
42.     return 0;
    
43. }

复制代码

五、总结

本文通过动态规划与树形结构的结合，巧妙解决了CTSC选课中的依赖关系问题。关键在于利用虚拟根节点统一入口，分组背包优化组合选择，避免了复杂搜索。该思路可扩展至其他树形依赖优化场景，如项目调度、资源分配等。建议读者结合代码注释深入理解状态转移逻辑，并尝试优化时间复杂度（如记忆化搜索或迭代优化）

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