鸿 网 互 联 www.68idc.cn

qiuzhijieluojianping的专栏

来源:互联网 作者:佚名 时间:2015-01-01 11:32
这是一篇关于动态规划的思考文章,主要讲了我对动态规划的一些思考与总结。

动态规划 & 思索

1 首先要先分析问题的结构,也记得自顶向下的去考虑一个问题,使用自顶向下的想法是在尝试着使用递归的方法,递归的过程中就会出现子问题,然后我们在去分析如果直接使用分治的方法的时间复杂性是多少,如果是指数级别的,那么我们就要进行第二步的思索。

2 这些自问题是否是独立的,如果不是独立的,那么自问题的个数是否是有多项式级别的,如果这个问题的子问题之间有交叉,而且子问题的个数是有限的,那么请进入第三步的思考方式?

3 子问题之间是否可以互相依赖,比如最优性的依赖,如果一个问题是的解是最有的,那么它的子问题的答案也应该是最优的,这个往往可以使用剪切粘贴的策略给予证明,也就是假设问题的子问题不是最优的,那么这时候就可以使用一个更好的解答来代替原来的子问题的解答,这样就可以得到一个更好的答案了,于是找到了矛盾。

如果一个问题满足上面的三个条件,我向这个问题基本上就是可以使用动态规划方法来解决了。

公司聚会问题

今天看了一个公司聚会计划的题目,觉得很有意思?

Stewart教授是一家公司总裁的顾问,这家公司计划一个公司聚会。这个公司有一个层次式的结构;也就是说,管理关系形成一棵以总裁为根的树。人事部给每个雇员以喜欢聚会的程度来排名,这是个实数。为了使每个参加者都喜欢这个聚会,总裁不希望一个雇员和他(她)的直接上司同时参加。

Stewart教授面对一棵描述公司结构的树,使用了左子女、右兄弟表示法。树中每个结点除了包含指针,还包含雇员的名字和该雇员喜欢聚会的排名。描述一个算法,它生成一张客人列表,使得客人喜欢聚会的程度的总和最大。分析你的算法的执行时间。


如何才能求出以A为根的最大收益,显然这时候根据题目的要求,如果A参加了聚会,那么B,C,D就不可以参加聚会了,如果A不参加聚会,那么B,C,D都有机会参加聚会,但是并不是说A不参加聚会,B,C,D就一定要参加聚会。经过上面的递推公式,我们还不能很好的编写动态规划的程序,现在我们来分析一下,其实我们会发现这个处理过程有点类似树的后序遍历,也就是要先访问完所有的儿子节点再来访问图本身这个节点。但是如果直接使用深度优先搜索的方法的话是不是也就可以了,当所有的儿子节点都访问我之后,就直接可以访问父节点了。当然为了使得能够直接获取儿子节点的信息,我们希望能够直接保存已经处理过的根节点。


其中

代表的是以A为根节点的最大收益值,

代表的是以A为根节点并且A参与使得最大收益值,而

代表的是以A为根节点并且A不参与其中的最大收益值。具体的代码如下:

// // Meeting.h // HelloWorld // // Created by jackqiu on 14-12-31. // Copyright (c) 2014年 jackqiu. All rights reserved. // #ifndef HelloWorld_Meeting_h #define HelloWorld_Meeting_h #include "TreeNode.h" struct MeetNode { MeetNode* child,*subling;//左儿子,有兄弟的表示方法 int key,_key;//参与时的最大收益值 int val;//该节点的收益值 MeetNode(int k1,int k2):key(k1),_key(k2) { child = NULL; subling = NULL; } MeetNode(int _val):val(_val) { key =0; _key = 0; child = nullptr; subling = nullptr; } }; class Meeting { //#define MAX_NODE 100 public: int maxProfile(MeetNode* root) { maxMeetingProfile(root); if(root==nullptr) return 0; int max = root->key>root->_key?root->key:root->_key; return max; } private: void maxMeetingProfile(MeetNode *root) { if(root->child) {//如果存在儿子节点就先将所有的儿子节点的收益值都先求出来 MeetNode* firstChild = root->child; maxMeetingProfile(firstChild); while(firstChild->subling) { maxMeetingProfile(firstChild->subling); firstChild = firstChild->subling; } } else//如果节点是叶子节点那么,该节点参与其中的收益就是val,而不参与其中的收益就为0 { root->key = root->val; root->_key = 0; return; } //root 参与 MeetNode* firstChild = root->child; int sum = firstChild->_key+root->val; while(firstChild->subling) { sum+=firstChild->subling->_key; firstChild = firstChild->subling; } //root 不参与的时候的最大收益值 firstChild = root->child; sum = 0; int max = firstChild->key>firstChild->_key?firstChild->key:firstChild->_key; sum+=max; while(firstChild->subling) { max = firstChild->subling->key>firstChild->subling->_key?firstChild->subling->key:firstChild->subling->_key; sum+=max; firstChild = firstChild->subling; } } }; #endif

那么如何使用刚才说过的三步思考方式去思考这个问题呢?


  • 整齐打印问题的思考

    网友评论
    <