算法动态规划

树形背包

字数统计: 1.8k字   |   阅读时长: 8分

摘要: 树形背包

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

本文我们以一个模板题看一下背包问题的变种之一：树形背包。树形背包问题是 树形DP 和 分组背包 的应用。

树形背包问题

有 N 个物品和一个容量是 V 的背包。

物品之间具有依赖关系，且依赖关系组成一棵树的形状。如果选择一个物品，则必须选择它的父节点。

如果选择物品5，则必须选择物品1和2。这是因为2是5的父节点，1是2的父节点。

每件物品的编号是 i，体积是 vi，价值是 wi，依赖的父节点编号是 pi。物品的下标范围是 1…N。

求解将哪些物品装入背包，可使物品总体积不超过背包容量，且总价值最大。

输出最大价值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
输入格式
第一行有两个整数 N，V，用空格隔开，分别表示物品个数和背包容量。
接下来有 N 行数据，每行数据表示一个物品。
第 i 行有三个整数 vi,wi,pi，用空格隔开，分别表示物品的体积、价值和依赖的物品编号。
如果 pi=−1，表示根节点。 数据保证所有物品构成一棵树。

输出格式
输出一个整数，表示最大价值。

数据范围
1<=N,V<=100
1<=vi,wi<=100

父节点编号范围：
内部结点：1<=pi<=N;
根节点 pi=−1;

输入样例
5 7
2 3 -1
2 2 1
3 5 1
4 7 2
3 6 2
输出样例：
11

算法：树形DP

1
2
3
4
5
6
dp[x][j] := 选择节点 x 且容量为 j 时，以 x 为根的子树能取到的最大价值

dp[x][j] = max(dp[x][j - k] + dp[y][k])   k 是分配给子节点 y 的体积, j - k 是留给 x 的体积
    其中 y 为 x 的子节点
         v[x] <= j <= V
         0 <= k <= j - v[x]

这个转移方程的形式是分组背包的模型。当前节点为 x，可用的体积为 j，对每个 x 的子节点 y，每个子树都可以选择 k = 0 ~ j - v[u] 的任一个体积 k。

如果把每个子树 y 视为一个虚拟物品组，共 j - v[u] 个虚拟物品，该分组可以从 0 ~ j - v[u] 中选择一个体积为 k 的虚拟物品，对应的价值为 dp[y][k]。

代码 (C++)

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
#include <iostream>
#include <vector>
using namespace std;

void dfs(int x, int V, vector<vector<int> >& dp, vector<vector<int> >& g, vector<int>& v, vector<int>& w)
{
    //点x必须选，所以初始化 dp[x][v[x] ~ m]= w[x]
    for(int i = v[x]; i <= V; i++) 
        dp[x][i] = w[x]; 
    for(int y: g[x])
    {
        dfs(y, V, dp, g, v, w);
        for(int j = V; j >= v[x]; j--) 
        {
            // j的范围为 v[x]~V, 小于 v[x] 无法选择以 x 为子树的物品
            for(int k = 0; k <= j - v[x]; k++) 
            {
                //分给子树 y 的空间不能大于j-v[x],不然都无法选根物品x
                dp[x][j] = max(dp[x][j], dp[x][j-k] + dp[y][k]);
            }
        }
    }
}

int main()
{
    int N,V;
    cin >> N >> V;
    vector<int> v(N + 1, 0);
    vector<int> w(N + 1, 0);

    // dp[x][v] := 选择以x为子树的物品，在容量不超过v时所获得的最大价值
    vector<vector<int> > dp(N + 1, vector<int>(V + 1, 0));
    vector<vector<int> > g(N + 1, vector<int>());

    int root;
    for(int i = 1; i <= N; i++)
    {
        int fa;
        cin >> v[i] >> w[i] >> fa;
        if(fa == -1)
            root = i;
        else
            g[fa].push_back(i);
    }

    dfs(root, V, dp, g, v, w);

    cout << dp[root][V];
    return 0;
}

$3 题目

286. 选课

学校实行学分制。

每门的必修课都有固定的学分，同时还必须获得相应的选修课程学分。

学校开设了 N 门的选修课程，每个学生可选课程的数量 M 是给定的。

学生选修了这 M 门课并考核通过就能获得相应的学分。

在选修课程中，有些课程可以直接选修，有些课程需要一定的基础知识，必须在选了其他的一些课程的基础上才能选修。

每门课的直接先修课最多只有一门。

两门课可能存在相同的先修课。

你的任务是为自己确定一个选课方案，使得你能得到的学分最多，并且必须满足先修条件。

假定课程之间不存在时间上的冲突。

1
2
3
4
5
6
7
8
输入格式
输入文件的第一行包括两个整数 N、M（中间用一个空格隔开）其中 1<=N<=300,1<=M<=N。
接下来 N 行每行代表一门课，课号依次为 1，2，...，N。
每行有两个数（用一个空格隔开），第一个数为这门课先修课的课号（若不存在先修课则该项为 0），第二个数为这门课的学分。
学分是不超过 10 的正整数。

输出格式
输出一个整数，表示学分总数。

输入样例：
7 4
2 2
0 1
0 4
2 1
7 1
7 6
2 2
输出样例：
13

算法: 树形背包

首先设置一个虚拟根 root，将多棵树连接成一棵树。然后在整棵树上选 M + 1 门课，其中 root 必选。

1
2
3
4
5
6
7
8
状态定义
dp[u][t] := 在子树 u 上选 t 门课的最多学分

状态
dp[u][0] = 0

答案
dp[root][M + 1]

状态转移如下，其中 $v_{i}$ 为 u 的子节点，个数为 p。

代码 (C++)

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
#include <iostream>
#include <vector>

using namespace std;

void dfs(const vector<vector<int>>& g, int u, const int V, const vector<int>& w, vector<vector<int>>& dp)
{
    // u 必选，即至少选一门课，因此 dp[u][1 ~ V] = w[u] 而 dp[u][0] = 0
    for(int j = 1; j <= V; ++j)
        dp[u][j] = w[u];
    for(int v: g[u])
    {
        dfs(g, v, V, w, dp);
        for(int j = V; j >= 1; --j)
        {
            // 当前子树 u 对应的物品组的虚拟物品的体积为 j
            for(int k = 0; k <= j - 1; ++k)
            {
                // 从子树 v 中选择体积为 k 的虚拟物品，价值为 dp[v][k]
                dp[u][j] = max(dp[u][j], dp[u][j - k] + dp[v][k]);
            }
        }
    }
}

int main()
{
    int N, M;
    cin >> N >> M;
    vector<int> scores(N + 1);
    vector<vector<int>> g(N + 1);
    int root = 0; // 虚拟根
    for(int u = 1; u <= N; ++u)
    {
        int fa;
        cin >> fa;
        cin >> scores[u];
        g[fa].push_back(u);
    }
    vector<vector<int>> dp(N + 1, vector<int>(M + 2));
    // dp[u][j] := 在子树 u 上最多选 j 门课的最多学分
    // 一共 N + 1 门课，虚拟根视为一门学分为零的课
    dfs(g, root, M + 1, scores, dp);
    cout << dp[root][M + 1] << endl;
}
Share