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

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

2个月前 (07-04)

1997年CTSC选课问题(洛谷P2014)解题全解析:动态规划与树形结构实战 CTSC选课  动态规划 树形结构 分组背包 第1张

一、题目解读

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;
}

五、总结

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


原创内容 转载请注明出处

分享给朋友:

相关文章

力扣70题:告别暴力递归!从零实现记忆化搜索解法

力扣70题:告别暴力递归!从零实现记忆化搜索解法

题意解析:想象你站在楼梯底部,面前有n级台阶。每次你可以选择跨1级或2级台阶,最终到达顶端的路径有多少种不同的走法?这个问题本质上是在探索分叉决策的叠加效果——当我们把每个台阶处的选择看作二叉树的分支...

【蓝桥杯2015省赛解析】生命之树:树形DP解题全攻略(洛谷P8625代码详解)

【蓝桥杯2015省赛解析】生命之树:树形DP解题全攻略(洛谷P8625代码详解)

一、题目解读    “生命之树”是一道经典的树形结构问题,要求计算一棵带权树中,以某个节点为根的最大子树权值和。题目输入为n个节点及边信息,每个节点有权值wi,...

力扣931题最小下降路径和解析 动态规划解法 LeetCode解题技巧

力扣931题最小下降路径和解析 动态规划解法 LeetCode解题技巧

一、题目解读力扣931题「Minimum Falling Path Sum」(最小下降路径和)要求在一个n x n的整数矩阵中,计算从顶部到底部的最小路径和。路径只能从每个位置向下或对角线移动(即向下...

牛客25461题解析:花园喷泉距离优化算法(动态规划+后缀数组解法)

牛客25461题解析:花园喷泉距离优化算法(动态规划+后缀数组解法)

一、题目解读牛客25461题要求计算一个花园中n朵花到两个喷泉的最小距离平方和。用户需输入喷泉坐标(x1,y1)和(x2,y2),以及n朵花的坐标(x,y),通过合理分配每朵花到两个喷泉的距离,使总距...

【蓝桥杯国赛A组】冰山体积计算:动态规划与map统计的解题方案(洛谷P8767)

【蓝桥杯国赛A组】冰山体积计算:动态规划与map统计的解题方案(洛谷P8767)

一、题目解读本题为2021年蓝桥杯国赛A组题目“冰山”(洛谷P8767),要求处理冰山在融化与新生成过程中的体积变化。每日存在两种操作:冰山体积按固定值x融化(体积不足x的部分视为完全融化),以及新增...

【2020蓝桥杯国赛C组】补给题解析:从Floyd到动态规划的高效解法

【2020蓝桥杯国赛C组】补给题解析:从Floyd到动态规划的高效解法

一、题目解读2020年蓝桥杯国赛C组“补给”题目要求:给定n个村庄坐标及最大补给距离D,需判断是否所有村庄均可从总部(村庄0)直接或间接到达,并计算访问所有村庄的最小路径(即旅行商问题TSP)。题目核...

发表评论

访客

看不清,换一张

◎欢迎参与讨论,请在这里发表您的看法和观点。