《选课树形动态规划ppt课件.ppt》由会员分享，可在线阅读，更多相关《选课树形动态规划ppt课件.ppt（12页珍藏版）》请在三一办公上搜索。
1、选课,给定M门课程，每门课程有一个学分要从M门课程中选择N门课程，使得学分总和最大其中选择课程必须满足以下条件：每门课程最多只有一门直接先修课要选择某门课程，必须先选修它的先修课M,N=500,分析,每门课程最多只有1门直接先修课，如果我们把课程看成结点，也就是说每个结点最多只一个前驱结点。如果把前驱结点看成父结点，换句话说，每个结点只有一个父结点。显然具有这种结构的模型是树结构，要么是一棵树，要么是一个森林。这样，问题就转化为在一个M个结点的森林中选取N个结点，使得所选结点的权值之和最大。同时满足每次选取时，若选儿子结点，必选根结点的条件。,样例分析,如图1，为两棵树，我们可以虚拟一个结点，
2、将这些树连接起来，那么森林就转会为了1棵树，选取结点时，从每个儿子出发进行选取。显然选M=4时，选3，2，7，6几门课程最优。,动态规划,如果我们单纯从树的角度考虑动态规划，设以i为根结点的树选j门课程所得到的最大学分为f(i,j), 设虚拟的树根编号为0，学分设为0，那么，ans=f(0,n+1)如果树根选择1门功课，剩下j-1门功课变成了给他所有儿子如何分配的资源的问题，这显然是背包问题。设前k个儿子选修了x门课程的最优值为g(k,x)，则有其中: 0=x=j-1，ans=g(son(0),n+1),构造树结构,readln(n,m); inc(m); for i:=1 to n do 父
3、亲表示法构造树 begin readln(pri,vi); pr是前驱结点，v价值 inc(tpri); t记录结点的儿子个数 nepri,tpri:=i; ne记录树 end;for i:=0 to n do ts记录每个结点后代的个数 tsi:=tsi-1+ti+1;,rocedure work(now:longint);inline; var i,j,k,bas:longint; begin for i:=1 to tnow do work(nenow,i); bas:=tsnow-1+1; for i:=bas+1 to bas+tnow do fi,j表示i子树内选j的最大价值 fo
4、r j:=1 to m do begin gi,j是给每个节点分配的内部背包的空间 gi,j:=gi-1,j; i不选 for k:=1 to j do i选k门 if gi-1,j-k+fnenow,i-bas,kgi,j then begin gi,j:=gi-1,j-k+fnenow,i-bas,k; fai,j:=k;记录决策点 end; end; for i:=m downto 1 do计算fi,j fnow,i:=gtnow+bas,i-1+vnow; end;,进一步分析,上述状态方程，需要枚举每个结点的x个儿子，而且对每个儿子的选课选择，需要再进行递归处理。当然这样可以解决问题
5、，那么我们还有没有其他方法呢？,转化为二叉树,如果该问题仅仅只是一棵二叉树，我们对儿子的分配就仅仅只需考虑左右孩子即可，问题就变得很简单了。因此我们试着将该问题转化为二叉树求解。图2就是对图1采用孩子兄弟表示法所得到的二叉树,动态规划,仔细理解左右孩子的意义（如右图）：左孩子：原根结点的孩子右孩子：原根结点的兄弟也就是说，左孩子分配选课资源时，根结点必须要选修，而与右孩子无关。因此，我们设f(i,j)表示以i为根结点的二叉树分配j门课程的所获得的最大学分，则有，0=kjn, i (1.m)时间复杂度O(mn2),样例求解过程：初始f(i,0)=0f(6,1)=6, f(5,1)=max1,6=
6、6, f(7,1)=2f(4,1)=max1,2=2, f(1,1)=max1,f(4,1)=2f(3,1)=4, f(2,1)=max1,4=4f(5,2)=7f(7,2)=maxf(5,1)+2=8f(4,2)=maxf(7,2),f(7,1)+1=8 f(1,2)=maxf(4,2),f(4,1)+2=8f(2,2)=maxf(1,1)+1, f(3,1)+1)=5f(7,3)=9f(4,3)=maxf(7,2)+1,f(7,3)=9f(1,3)=maxf(4,2)+1,f(4,3)=9 f(2,3)=maxf(1,1)+f(3,1)+1,f(1,2)+1=9f(2,4)=maxf(1,
7、3)+1, f(1,2)+f(3,1)+1=max9+1,8+4+1=13,/读入数据 ,转化为孩子兄弟表示 fin n m; scoren+1 = 0; brothern+1 = 0; / 输入数据并转化为左儿子右兄弟表示法 for (int i=1; i a b; if (a = 0) a = n + 1; scorei = b; brotheri = childa; childa = i; ,void dfs( int i, int j) if (visitedij) return; visitedij = 1; if (i=0 | j=0) return; dfs(brotheri, j); / 如果不选i，则转移到状态(brotheri, j) fij = fbrotherij; for (int k=0; k fij) fij = fbrotherik + fchildij-k-1 + scorei; ,
