动态规划之二叉苹果树及其变形

发表于 | 分类于 | | 阅读次数:

二叉苹果树作为树形规划的经典例题，对于我们学习动态规划有着很大的借鉴意义，本文通过介绍二叉苹果树的一种解法思路以及二叉苹果树的另一种变形，深入理解动态规划的思想和方式。

二叉苹果树

题目要求

有一棵苹果树，苹果树的是一棵完全二叉树，共N个节点，树节点编号为1~N，编号为1的节点为树根，边可理解为树的分枝，每个分支都长着若干个苹果（每条边有值对应树枝上的苹果数量），现在要要求减去若干个分支，保留M个分支，要求这M个分支的苹果数量最多。
【输入格式】
第 1 行 2 个数，N 和 Q(1<=Q<= N,1<N<=100)。
N 表示树的结点数，Q 表示要保留的树枝数量。接下来 N-1 行描述树枝的信息。
每行 3 个整数，前两个是它连接的结点的编号。第 3 个数是这根树枝上苹果的数量。
每根树枝上的苹果不超过 30000 个。
【输出格式】
一个数，最多能留住的苹果的数量。
【输入样例】

5 2
1 3 1
1 4 10
2 3 20
3 5 20

【输出样例】

21

解题思路

  • 要求的结果是以1号根节点为根的M个分支所能具有的最多苹果数量
  • 由于是完全二叉树，所以每个结点有且只有可能有两个儿子结点，否则就是叶子结点；
  • 使用一个vector<vector<pair<int, int>>>存储树的结构，将每条分支的权值分配给儿子结点；
  • 使用res[i][j]表示以i结点为根节点的j个分支能包含的最大苹果数量，使用tot[i]表示以i结点（包括i结点本身）为根节点的子树所包含的结点总数；
  • 使用动态规划的思路来进行求解，状态转移方程为：res[i][j] = max{res[i][j], res[i][j-k] + res[i_child][k]}，其中1<=k<j。
    注意：这里j需要从大到小遍历，这样当j=4时求取res[i][4]时，k=1,2,3时读取的res[i][3], res[i][2], res[i][1]因为之前的计算结果所以不包含i_child子树中的结点，其他同理，从而避免了重复的结点选择。
  • 使用深度优先搜索DFS来对树结构进行遍历，从下而上对各结点的状态方程进行求解；

最终代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <iostream>
#include <vector>
using namespace std;
int n, q;
vector<vector<pair<int, int>>> tree(101);//存储树结构
int res[101][101] = {0};//存储DP结果
int tot[101] = {0};//存储每个结点子树的结点总数

int dfs(int cur, int fa)
{
    tot[cur] = 1;
    for(int i = 0; i < tree[cur].size(); ++i)
    {
        int Child = tree[cur][i].first;
        if(Child ==  fa)
            continue;
        tot[cur] += dfs(Child, cur);
    }
    //分别对每个子树进行遍历
    for(int i = 0; i < tree[cur].size(); ++i)
    {
        int Child = tree[cur][i].first;
        int Value = tree[cur][i].second;
        if(Child == fa)
            continue;
        //j需要从大到小进行遍历
        for(int j = tot[cur]; j>1; --j)
        {
            for(int k = 1; (k<j)&&(k<=tot[Child]); ++k)
                //此前的res[cur][j]并不包含Child子树中的结点
                res[cur][j] = max(res[cur][j], res[cur][j-k] + res[Child][k] + Value);
        }
    }
    return tot[cur];
}

int main()
{
    cin >> n >> q;
    int a, b, v;
    for(int i = 1; i < n; ++i)
    {
        cin >> a >> b >> v;
        tree[a].push_back(make_pair(b, v));
        tree[b].push_back(make_pair(a, v));
    }
    dfs(1, -1);
    cout << res[1][q+1] << endl;
    for(int i = 1; i <= n; ++i)
        cout << tot[i] << " ";
    cout << endl;
    return 0;
}

二叉苹果树变形

题目描述

相对于二叉苹果树设定两个结点之间的分支上含有苹果的数量，现在设定每个结点都有一个权值，代表该结点上的苹果数量，现在仍然以1号结点为根节点，一共包含N个结点，求取当我进行剪枝之后所剩的M个结点（包括根结点）所能获得的最大的数量。并且，本次树结构可以是以1号结点为根结点的各种形状。
【输入】
每个测试点（输入文件）有且仅有一组测试数据。
每组测试数据的第一行为两个整数N、M，意义如前文所述。
每组测试数据的第二行为N个整数，其中第i个整数Vi表示标号为i的结点的评分
每组测试数据的第3~N+1行，每行分别描述一根木棍，其中第i+1行为两个整数Ai，Bi，表示第i根木棍连接的两个小球的编号。
【输出】
对于每组测试数据，输出一个整数Ans，表示使得涂漆结点的评分之和最高可能是多少。
【样例输入】

10 4
370 328 750 930 604 732 159 167 945 210
1 2
2 3
1 4
1 5
4 6
4 7
4 8
6 9
5 10

【样例输出】

2977

解题思路

  • 同上一题，使用vector<vector>对树的结构进行存储，各结点的权值存储到value[]数组中；
  • 使用num[]数组存储以各结点为根节点的子树中结点总数，df[i][j]表示以i结点为根节点的j个结点子树中可以包含的最大苹果数量；
  • 仍然是采用动态规划的方法，状态转移方程为：df[i][j] = max{df[i][j], df[i][j-k] + df[i_child][k]}，其中1<=k<j;
    注意这里j也一定要从大到小进行遍历，保证子树结点选择不重复。

最终代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
//这段代码很不错，树归的经典！！
#include <iostream>
#include <vector>
using namespace std;
int value[102] = {0};
int df[102][102] = {0};
int num[102] = {0};
vector<vector<int>> tree(102);
int n, p;

int dfs(int cur, int fa)
{
    num[cur] = 1;
    int len = tree[cur].size();
    for(int i = 0; i < len; ++i)
    {
        if(tree[cur][i] == fa)
            continue;
        num[cur] += dfs(tree[cur][i], cur);
    }
    for(int i = 0; i < len; ++i)
    {
        if(tree[cur][i] == fa)
            continue;
        //从大到小是精髓，保证了子树结点选择不重复
        for(int j = p; j > 1; --j) 
        {
            for(int k = 1; k < j && k <= num[tree[cur][i]]; ++k)
            {
                df[cur][j] = max(df[cur][j], df[cur][j-k] + df[tree[cur][i]][k]);
            }
        }
    }
    return num[cur];
}

int main()
{
    int a, b;
    cin >> n >> p;
    for(int i = 1; i <= n; ++i)
    {
        cin >> value[i];
    }
    for(int i = 1; i <= n; ++i)
    {
        df[i][1] = value[i];
    }
    for(int i = 1; i < n; ++i)
    {
        cin >> a >> b;
        tree[a].push_back(b);
        tree[b].push_back(a);
    }
    dfs(1, -1);
    cout << df[1][p] << endl;
    return 0;
}

总结

  • 对于动态规划中的树形规划，采用DFS深度优先搜索可以非常方便的完成从下到上的状态信息收集；
  • 树形规划一般需要对各子树进行遍历，在遍历过程中，根据状态转移方程，状态值由大到小进行遍历，从而保证原始状态不包含新子树中的结点，子树结点选择不会重复进行。
-------------本文结束感谢您的阅读-------------
0%