东莞建设网站官网住房和城乡资料汉中市住房和城乡建设局网站

东莞建设网站官网住房和城乡资料,汉中市住房和城乡建设局网站,网站开发项目经验和教训,品牌网络营销案例分析文章目录前言一、树形动态规划是什么#xff1f;二、对树形动态规划的分析1.分析具体实例2.树的构建过程以及最终的代码前言 上期文章#xff0c;我们讲了区间动态规划的内容#xff0c;如果对区间动态规划的内容还有疑问的话#xff0c;可以参考我的上期内容#xff0c;…文章目录前言一、树形动态规划是什么二、对树形动态规划的分析1.分析具体实例2.树的构建过程以及最终的代码前言上期文章我们讲了区间动态规划的内容如果对区间动态规划的内容还有疑问的话可以参考我的上期内容而这期我们就来讲解树形动态规划的内容话不多说我们直接开始。一、树形动态规划是什么要搞清楚这个问题我们首先要了解树这种数据结构树是一种非线性数据结构最上面的结点叫作树的根节点而其后面所跟着的结点叫作根的子节点同时其根结点也叫作父节点树是一种一对多的数据结构而树形动态规划就是利用如同树这种数据结构来解决相应的问题的动态规划如果对树这种数据结构不了解的读者可以先去了解一下这种结构再来学习这篇文章。二、对树形动态规划的分析1.分析具体实例我们以经典的问题没有上司的舞会为例某大学有 n 个职员编号为 1…n。他们之间有从属关系也就是说他们的关系就像一棵以校长为根的树父结点就是子结点的直接上司。现在有个周年庆宴会宴会每邀请来一个职员都会增加一定的快乐指数 r i但是呢如果某个职员的直接上司来参加舞会了那么这个职员就无论如何也不肯来参加舞会了。所以请你编程计算邀请哪些职员可以使快乐指数最大求最大的快乐指数。首先这种问题是一个典型的树形动态规划问题了解动态规划的知道求解动态规划问题的最重要的一步就是求出动态转移方程那么这种问题很明显就是先确认当前的状态由于当有上司在场时其职员就一定不会来而上司不再时职员可来可不来那么就需要记录职员的状态一确定是否来这个舞会。因此需要设置一个二维数组dp[MAX][2]来确定其状态在此例中结合树这种数据结构很容易想出用父节点来代表其上司而用子节点来代表其直属的职员我们用1代表这个人来的舞会用0代表这个人不来舞会用u代表上司v代表其直属下属即可推得状态转移方程为dp[u][1]dp[v[0],dp[u][0]max(dp[v][0],dp[v][0]),其中dp[j][0/1]代表这个人来舞会或者不来舞会所获得的快乐指数当动态转移方程被推出时问题就在于如何利用树形结构来求解最大快乐指数在树这种数据结构中有两种遍历方法一个叫作深度优先遍历另一个叫作广度优先遍历我们一深度优先遍历为例如果不太了解这两种遍历的读者可以自行查询资料再来看这篇文章其实对于树形动态规划而言往往是使用深度优先遍历这种暴力法来求解问题利用此种方法可以对问题进行求解不过在此之前需要先构建好树这种数据结构来方便我们使用深度优先遍历。构建树的方法随后会在下面的代码中给出那么绕了这么大一圈我们终于分析完了树形动态规划的问题。2.树的构建过程以及最终的代码此问题求解的代码如下#includeiostream#includealgorithmusing namespace std;constintMAXN6010;// 数据规模最大6000// 纯数组模拟邻接表替代结构体intto[MAXN];// to[i]表示第i条边指向的子节点intnext_edge[MAXN];// next_edge[i]表示第i条边的下一条边索引inthead[MAXN];// head[u]表示以u为父节点的第一条边的索引inthappy[MAXN];// 每个职员的快乐指数intdp[MAXN][2];// dp[u][0]不选u, dp[u][1]选ubool is_root[MAXN];// 标记是否是根节点intedge_cnt;// 边的计数器// 添加边u是父节点v是子节点voidadd_edge(intu,intv){to[edge_cnt]v;// 第edge_cnt条边指向vnext_edge[edge_cnt]head[u];// 指向上一条边head[u]edge_cnt;// 更新head[u]为当前边索引}// 深度优先搜索遍历树计算dp值voiddfs(intu){// 初始化状态dp[u][1]happy[u];// 选u初始快乐值为自己dp[u][0]0;// 不选u初始快乐值为0// 链式遍历u的所有子节点纯数组实现for(intihead[u];i!-1;inext_edge[i]){intvto[i];// 获取当前边指向的子节点vdfs(v);// 递归处理子节点// 状态转移dp[u][1]dp[v][0];// 选u则子节点必不选dp[u][0]max(dp[v][0],dp[v][1]);// 不选u则子节点选/不选取最大}}intmain(){intn;cinn;// 初始化数组for(inti1;in;i){head[i]-1;// 初始无任何边is_root[i]true;// 初始假设都是根节点}edge_cnt0;// 边计数器清零// 输入快乐指数for(inti1;in;i){cinhappy[i];}// 输入上下级关系构建树for(inti0;in-1;i){intl,k;cinlk;// k是l的直接上司add_edge(k,l);// 添加k到l的边l是k的子节点is_root[l]false;// l有上司不是根节点}// 找根节点校长introot0;for(inti1;in;i){if(is_root[i]){rooti;break;}}// 计算DP值dfs(root);// 输出最大值coutmax(dp[root][0],dp[root][1])endl;return0;}# 总结 树形动态规划的问题主要是首先先求解出动态转移方程然后再以此为核心利用深度优先搜索构建出树这种数据结构最后再进行求解。 最后如果文章有内容上的问题欢迎私信我指正对此类讲解感兴趣的读者可以关注一下。 最后的最后感谢大家的观看我们下期再见。