阅读 44

P2015 二叉苹果树

状态表示:
\(dp[u][j]\):表示以结点u为根的子树上留j条边时的最多苹果数量。

状态转移:
状态转移方程如何设计?下面给出2种思路,二叉树方法、多叉树(一般性)方法。
(1)二叉树
本题是一棵二叉树,根据二叉树的特征,考虑u的左右子树,如果左子树\(l\)共留\(k\)条边(不包含\(u \rightarrow l\)这条边),右子树\(r\)则留\(j - k - 2\)条边(同样不包含\(u \rightarrow r\)这条边),减\(2\)的原因是除去\(u \rightarrow l\)以及\(u \rightarrow r\),用\(k\)\([0, j-2]\)内遍历不同的分割。
转移方程如下:

\[f(u,j)=\max(f(l,j-1)+w[u\rightarrow l],f(r,j-1)+w[u\rightarrow r],\\f(l,k)+f(r,j-2-k)+w[u\rightarrow l]+w[u\rightarrow r]) \]

其中,\(f(l,j-1)\)表示\(j\)条边全部保留在左子树,\(f(r,j-1)\)表示\(j\)条边全部保留在右子树。\(f(l,k)\)\(f(r,j-2-k)\)表示左子树保留\(k\)条边,右子树保留\(j-k-2\)条边。

边界:
\(f(leaf,j)=0\)\(f(u,0)=0\)

注意点

首先需要建树,原题输入数据并没有明确给出父子关系。建树后可将边权转化为儿子节点的点权。

const int N=110;
PII tree[N];
vector g[N];
int f[N][N];
int apple[N];
int n,m;

void build(int u,int fa)
{
    for(int i=0;i>n>>m;

    for(int i=0;i>a>>b>>c;
        g[a].pb({b,c});
        g[b].pb({a,c});
    }
    
    build(1,-1);

    cout<

(2)多叉树
状态转移:

\[f(u,j)=\max(f(u,j),f(u,j-k-1)+f(v,k)+w(u\rightarrow v)) \]

\(v\)\(u\)的一个子结点。\(dp[u][j]\)的计算分为2部分:

  1. \(dp[v][k]\):在\(v\)上留\(k\)个边;
  2. \(dp[u][j-k-1]\):除了\(v\)上的\(k\)个边,以及边\([u,v]\),那么以\(u\)为根的这棵树上还有\(j-k-1\)个边,它们在u的其他子结点上。
const int N=110;
vector g[N];
int f[N][N];
int apple[N];
int n,m;

void dfs(int u,int fa)
{
    for(int i=0;i=1;j--)
            for(int k=0;k>n>>m;

    for(int i=0;i>a>>b>>c;
        g[a].pb({b,c});
        g[b].pb({a,c});
    }

    dfs(1,-1);

    cout<

有一些树形DP问题,可以抽象为背包问题,被称为“树形依赖的背包问题”。例如上面的题目“二叉苹果树”,可以建模为“分组背包”(注意与普通分组背包的区别是,这里的每个组可以选多个物品,而不是一个):
(1)分组。根结点u的每个子树是一个分组。
(2)背包的容量。把u为根的整棵树上的树枝数,看成背包容量。
(3)物品。把每个树枝看成一个物品,体积为1,树枝上的苹果数量看成物品的价值。
(4)背包目标。求能放到背包的物品的总价值最大,就是求留下树枝的苹果数最多。

分组背包的代码和“二叉苹果树”的代码很像,下面贴出2个代码帮助理解。
(1)分组背包的代码。

for(int i = 1; i <= n; i++)                 //遍历每个组
    for(int j = C; j>=0; j--)               //背包总容量C
        for(int k = 1; k <= m; k++)         //用k遍历第i组的所有物品
            if(j >= c[i][k])                //第k个物品能装进容量j的背包
               dp[j] = max(dp[j], dp[j-c[i][k]] + w[i][k]);    //第i组第k个

(2)树形dp代码。下面是洛谷P2015部分代码。

for(int i = 0; i < edge[u].size(); i++) {    //把u的每个子树看成一个组
    ......
    for(int j = m; j >= 1; j--)         //把u的枝条总数看成背包容量
        for(int k = 0; k < j ; k++)      //用k遍历每个子树的每个枝条
            dp[u][j] = max(dp[u][j], dp[u][j-k-1] + dp[v][k] + w);

树形背包问题的状态定义,一般用dp[u][j]表示以点u为根的子树中,选择j个点(或j个边)的最优情况。

原文:https://www.cnblogs.com/fxh0707/p/14640468.html

文章分类
代码人生
文章标签
版权声明:本站是系统测试站点,无实际运营。本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容, 请发送邮件至 gxwowoo@163.com 举报,一经查实,本站将立刻删除。
相关推荐