朱全民树型动态规划.ppt

《朱全民树型动态规划.ppt》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、树型动态规划加分二叉树给定一个中序遍历为1,2,3,…,n的二叉树每个结点有一个权值定义二叉树的加分规则为：左子树的加分×右子树的加分＋根的分数若某个树缺少左子树或右子树，规定缺少的子树加分为1。构造符合条件的二叉树该树加分最大输出其前序遍历序列样例中序遍历为1,2,3,4,5的二叉树有很多，下图是其中的三棵，其中第三棵加分最大，为145.分析性质：中序遍历是按“左-根-右”方式进行遍历二叉树，因此二叉树左孩子遍历序列一定在根结点的左边，右孩子遍历序列一定在根结点的右边！因此，假设二叉树的根结点为k，那么中序遍历为1,2,…,n的遍历序列，左孩子序列为1,2

2、,…,k-1，右孩子序列为k+1,k+2,…,n，如下图动态规划设f(i,j)中序遍历为i,i+1,…,j的二叉树的最大加分，则有：f(i,j)=max{f[i,k-1]*f[k+1,j]+d[k]}显然f(i,i)=d[i]答案为f(1,n)1<=i<=k=<=j<=n时间复杂度O(n3)要构造这个树，只需记录每次的决策值，令b(i,j)=k，表示中序遍历为i,i+1,…,j的二叉树的取最优决策时的根结点为k最后前序遍历这个树即可。选课给定M门课程，每门课程有一个学分要从M门课程中选择N门课程，使得学分总和最大其中选择课程必须满足以下条件：每门课程最多只有

3、一门直接先修课要选择某门课程，必须先选修它的先修课M,N<=500分析每门课程最多只有1门直接先修课，如果我们把课程看成结点，也就是说每个结点最多只一个前驱结点。如果把前驱结点看成父结点，换句话说，每个结点只有一个父结点。显然具有这种结构的模型是树结构，要么是一棵树，要么是一个森林。这样，问题就转化为在一个M个结点的森林中选取N个结点，使得所选结点的权值之和最大。同时满足每次选取时，若选儿子结点，必选根结点的条件。样例分析如图1，为两棵树，我们可以虚拟一个结点，将这些树连接起来，那么森林就转会为了1棵树，选取结点时，从每个儿子出发进行选取。显然选M=4时，选

4、3，2，7，6几门课程最优。转化为二叉树如果该问题仅仅只是一棵二叉树，我们对儿子的分配就仅仅只需考虑左右孩子即可，问题就变得很简单了。因此我们试着将该问题转化为二叉树求解。图2就是对图1采用孩子兄弟表示法所得到的二叉树动态规划仔细理解左右孩子的意义（如右图）：左孩子：原根结点的孩子右孩子：原根结点的兄弟也就是说，左孩子分配选课资源时，根结点必须要选修，而与右孩子无关。因此，我们设f(i,j)表示以i为根结点的二叉树分配j门课程的所获得的最大学分，则有，0<=k

5、f(5,1)=max{1,6}=6,f(7,1)=2f(4,1)=max{1,2}=2,f(1,1)=max{1,f(4,1)}=2f(3,1)=4,f(2,1)=max{1,4}=4f(5,2)=7f(7,2)=max{f(5,1)+2}=8f(4,2)=max{f(7,2),f(7,1)+1}=8f(1,2)=max{f(4,2),f(4,1)+2}=8f(2,2)=max{f(1,1)+1,f(3,1)+1)}=5f(7,3)=9f(4,3)=max{f(7,2)+1,f(7,3)}=9f(1,3)=max{f(4,2)+1,f(4,3)}=9f(2,

6、3)=max{f(1,1)+f(3,1)+1,f(1,2)+1}=9f(2,4)=max{f(1,3)+1,f(1,2)+f(3,1)+1}=max{9+1,8+4+1}=13//读入数据,转化为孩子兄弟表示fin>>n>>m;score[n+1]=0;brother[n+1]=0;//输入数据并转化为左儿子右兄弟表示法for(inti=1;i<=n;++i){inta,b;fin>>a>>b;if(a==0)a=n+1;score[i]=b;brother[i]=child[a];child[a]=i;}voiddfs(inti,intj){if(visi

7、ted[i][j])return;visited[i][j]=1;if(i==0

8、

9、j==0)return;dfs(brother[i],j);//如果不选i，则转移到状态(brother[i],j)f[i][j]=f[brother[i]][j];for(intk=0;kf[i][j])f[i]

10、[j]=f[brother[i]][k]+f[chi