树形背包

  |  

摘要: 树形背包

【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】
我的网站:潮汐朝夕的生活实验室
我的公众号:算法题刷刷
我的知乎:潮汐朝夕
我的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