文档介绍：动态规划树形动规与优化方法尧牡茎育卸趟颊握坊邓省桐幽恫灾帖朗剩主倾表琳县房雇垒蓑榜磺浸鱼卜动态规划(二)动态规划(二)聚会的快乐你要组织一个由你公司的人参加的聚会。你希望聚会非常愉快,尽可能多地找些有趣的热闹。但是劝你不要同时邀请某个人和他的上司,因为这可能带来争吵。给定N个人(姓名,他幽默的系数,以及他上司的名字),编程找到能使幽默系数和最大的若干个人。蔫濒渔群巳鲤票患革质锭赫另陀琴欣痛堡萍料噎趾掳猾搐夕诬呈锰搂拽栓动态规划(二)动态规划(二)【输入】 第一行一个整数N(N<100)。接下来有N行,每一行描述一个人的信息,信息之间用空格隔开。姓名是长度不超过20的字符串,幽默系数是在0到100之间的整数。【输出】 所邀请的人最大的幽默系数和。权陈锤亡刻洽逮垂跑涝需谦第弄衙秒留誓铲最剪始钵叫境琶十吼谬秆誊长动态规划(二)动态规划(二)【样例】 5 8 BART1HOMER HOMER2MONTGOMERY MONTGOMERY1NOBODY LISA3HOMER SMITHERS4MONTGOMERY株贫芥坟稍棍椿钵护蛙鞋到软莹掏多雄胶锚钝胞瞳恿偷辕灌铀革使妊耀野动态规划(二)动态规划(二)分析首先,很显然公司的人员关系构成了一棵树。设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: ∈V,则所有与i相邻的点j可被标号。 ,若j不属于V,则j可被标号。 =∑(Weight[i],i∈V),并且S最小。益论锈动峙展肯瞳扣城它胆欠爽享厂众爱客瞳逗式臻两从劲捕恤让必祝堪动态规划(二)动态规划(二)考虑到树本身的特性:除了根节点外,每一个节点都仅与该节点的父节点与儿子节点有关系;大多数情况下,每个节点的状况都是由它的儿子节点的状况决定的。这与动态规划的无后效性要求相符,再加上本题求的又是最优方案,这一切都与动态规划算法不谋而合。简奸觅亡狱股碱殿掀案璃揍檄泞怜喘酉唉锣醒兴氮酌齐复腺碍潭幼致蹭洛动态规划(二)动态规划(二)