首页 > 代码库 > 树形动态规划

树形动态规划

问题可以分解成若干相互联系的阶段,在每一个阶段都要做出决策,全部过程的决策是一个决策序列。要使整个活动的总体效果达到最优的问题,称为多阶段决策问题。动态规划就是解决多阶段决策最优化问题的一种思想方法。
 

阶段

将所给问题的过程,按时间或空间特征分解成若干相互联系的阶段,以便按次序去求每阶段的解

状态

各阶段开始时的客观条件叫做状态。

决策

当各段的状态取定以后,就可以做出不同的决定,从而确定下一阶段的状态,这种决定称为决策。

策略

由开始到终点的全过程中,由每段决策组成的决策序列称为全过程策略,简称策略。

状态转移方程

前一阶段的终点就是后一阶段的起点,前一阶段的决策选择导出了后一阶段的状态,这种关系描述了由k阶段到k+1阶段状态的演变规律,称为状态转移方程。

目标函数与最优化概念

目标函数是衡量多阶段决策过程优劣的准则。最优化概念是在一定条件下找到一个途径,经过按题目具体性质所确定的运算以后,使全过程的总效益达到最优。
大多数动规都是在一维二维这种规则的背景下的,可以解决的问题比较局限,而树作为一种特殊的图,可以描述比较复杂的关系,再加上树的递归定义,是一种非常合适动规的框架,树型动态规划就成为动规中很特殊的一种类型。
 

树形动态规划基本上可以分为2个部分,一个是建树,另一个就是动态规划,一个好的数据结构,能使你编程非常容易,这也是树形动态规划的难点之一

典型例题

没有上司的晚会等
【问题描述】
有个公司要举行一场晚会。为了让到会的每个人不受他的直接上司约束而能玩得开心,公司领导决定:如果邀请了某个人,那么一定不会再邀请他的直接的上司,但该人的上司的上司,上司的上司的上司……都可以邀请。已知每个人最多有唯一的一个上司。
已知公司的每个人参加晚会都能为晚会增添一些气氛,求一个邀请方案,使气氛值的和最大。
【输入:】
第1行一个整数N(1<=N<=6000)表示公司的人数。
接下来N行每行一个整数。第i行的数表示第i个人的气氛值x(-128<=x<=127)。
接下来每行两个整数L,K。表示第K个人是第L个人的上司。
输入以0 0结束。
【输出】:
一个数,最大的气氛值和。
【样例输入】
7
1
1
1
1
1
1
1
1 3
2 3
6 4
7 4
4 5
3 5
0 0
【样例输出】
5
【分析】
如上例,上司与小兵之间的关系构成一棵树。
5
| \
3 4
| \ | \
1 2 6 7
又是求最优解,并且每一个节点的取舍关乎到全局 因此,此题可用树形动态规划
我们可用f[v][0]存储不选编号为V的节点的最优解,f[v][1]存储选编号为V的节点的最优解
 
//大数组的定义最好不要写在函数里,这样会使函数栈控件不足 

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define M 1000	//数组最大长度 

int shu[M][M],xb[M][M],shs[M],qf[M],f[M][2];
int main()
{
	
	int i,j,l,k,n,maxlev,s,x,a,b;
	
	memset(shu,0,sizeof(shu));
	memset(xb,0,sizeof(xb));
	memset(shs,0,sizeof(shs));
	memset(f,0,sizeof(f));
	
	//1、建树 
	scanf("%d",&n);
	for(i=1;i<=n;i++)scanf("%d",&qf[i]);
	
	l=k=1;
	while(l&&k)
	{
		scanf("%d%d",&l,&k);
		shs[l]=k;
		xb[k][0]++;
		xb[k][xb[k][0]]=l;
	}
	
	maxlev=-1;
	for(i=1;i<=n;i++)
	{
		x=shs[i],s=1;
		while(x!=0){s++;x=shs[x];}
		shu[s][0]++;
		shu[s][shu[s][0]]=i;
		if(s>maxlev)maxlev=s;
	}
	
	//2、动态规划
	 for(i=maxlev;i>0;i--)
	 {
	 	for(j=1;j<=shu[i][0];j++)
	 	{
	 		if(xb[shu[i][j]][0]==0)
	 		{
	 			f[shu[i][j]][0]=0;
	 			f[shu[i][j]][1]=qf[shu[i][j]];
	 		}
	 		else
	 		{
	 			f[shu[i][j]][0]=0;
	 			f[shu[i][j]][1]=qf[shu[i][j]];
	 			for(k=1;k<=xb[shu[i][j]][0];k++)
	 			{
	 				a=f[xb[shu[i][j]][k]][0];b=f[xb[shu[i][j]][k]][1];
	 				
	 				f[shu[i][j]][1] +=a;//如果要当前节点,则不能取下部节点 
	 				
	 				//如果不要当前节点,则可要可不要下部节点,取使得气氛值最大的方案 
					if(b>a)a=b;
	 				f[shu[i][j]][0] +=a;
	 			}
	 		}//状态转移 
	 	}
	 }
	 
	 s=0;
	 for(i=1;i<=shu[1][0];i++)//从树根获取最优方案
	 {
	 	a=f[shu[1][i]][0];b=f[shu[1][i]][1];
	 	if(b>a)a=b;
	 	s+=a;
	 }
	 
	 printf("最大气氛值:%d\n",s); 
	
	return 0;
}

树形动态规划