文档介绍：动态规划动态规划树形动规与优化方法树形动规与优化方法聚会的快乐?你要组织一个由你公司的人参加的聚会。你希望聚会非常愉快,尽可能多地找些有趣的热闹。但是劝你不要同时邀请某个人和他的上司, 因为这可能带来争吵。给定 N个人(姓名,他幽默的系数,以及他上司的名字),编程找到能使幽默系数和最大的若干个人。?【输入】?第一行一个整数 N(N<100) 。接下来有 N 行,每一行描述一个人的信息,信息之间用空格隔开。姓名是长度不超过 20 的字符?串,幽默系数是在 0到 100 之间的整数。?【输出】?所邀请的人最大的幽默系数和。?【样例】? ?58 ? BART 1 HOMER ? HOMER 2 MONTGOMERY ? MONTGOMERY 1 NOBODY ? LISA 3 HOMER ? SMITHERS 4 MONTGOMERY 分析首先,很显然公司的人员关系构成了一棵树。设 f[a] 为a参加会议的情况下,以他为根的子树取得的最大幽默值; g[a] 为a不参加会议的情况下, 以他为根的子树取得的最大幽默值。那么,状态转移方程就是: f[a]=g[b1]+g[b2]+ …+g[bk]+1 g[a]=max(f[b1], g[b1])+max(f[b2], g[b2])+ …+max(f[bk], g[bk]) ?其中 b1, b2, …, bk 为a的子结点。最后的答案就是 max(f[root], g[root]) , root 是树根。三色二叉树( tro ) ?见文本树形动态规划(皇宫看守) ?太平王世子事件后,陆小凤成了皇上特聘的御前一品侍卫。皇宫以午门为起点,直到后宫嫔妃们的寝宫,呈一棵树的形状;某些宫殿间可以互相望见。大内保卫森严,三步一岗,五步一哨,每个宫殿都要有人全天候看守, 在不同的宫殿安排看守所需的费用不同。可是陆小凤手上的经费不足,无论如何也没法在每个宫殿都安置留守侍卫。编程任务:帮助陆小凤布置侍卫, 在看守全部宫殿的前提下,使得花费的经费最少。?数据输入:输入数据由文件名为 的文本文件提供。输入文件中数据表示一棵树,描述如下: ?第1行n,表示树中结点的数目。?第2行至第 n+1 行,每行描述每个宫殿结点信息,依次为:该宫殿结点标号 i ( 0<i<=n ),在该宫殿安置侍卫所需的经费 k,该边的儿子数 m,接下来 m 个数,分别是这个节点的 m个儿子的标号 r1, r2, ..., rm 。? 对于一个 n( 0 < n <= 1500 )个结点的树,结点标号在 1到n之间,且标号不重复。数据输出:输出到 文件中。输出文件仅包含一个数,为所求的最少的经费。输入数据示例输出数据示例 25 问题分析求给定的带权树的符合下面条件的子顶点集合 V: i∈V,则所有与 i相邻的点 j可被标号。 j,若 j不属于 V,则 j可被标号。 3. S= ∑( Weight[i] ,i∈V),并且 S最小。考虑到树本身的特性:除了根节点外,每一个节点都仅与该节点的父节点与儿子节点有关系;大多数情况下,每个节点的状况都是由它的儿子节点的状况决定的。这与动态规划的无后效性要求相符,再加上本题求的又是最优方案,这一切都与动态规划算法不谋而合。