首页 > 代码库 > 树形动态规划
树形动态规划
问题可以分解成若干相互联系的阶段，在每一个阶段都要做出决策，全部过程的决策是一个决策序列。要使整个活动的总体效果达到最优的问题，称为多阶段决策问题。动态规划就是解决多阶段决策最优化问题的一种思想方法。
阶段
将所给问题的过程，按时间或空间特征分解成若干相互联系的阶段，以便按次序去求每阶段的解
状态
各阶段开始时的客观条件叫做状态。
决策
当各段的状态取定以后，就可以做出不同的决定，从而确定下一阶段的状态，这种决定称为决策。
策略
由开始到终点的全过程中，由每段决策组成的决策序列称为全过程策略，简称策略。
状态转移方程
前一阶段的终点就是后一阶段的起点，前一阶段的决策选择导出了后一阶段的状态，这种关系描述了由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;
}
树形动态规划
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。