$\LARGE\color{orange}{刷题日记(算法提高课)}$
回顾线性背包的定义:考虑前 $i$ 个物品,在体积不超过 $j$ 下的最大价值
这里树型背包的定义改为:考虑以节点 $u$ 为根的子树,在体积不超过 $j$ 下的最大价值
在线性背包的定义中,$f[i]$ 的状态只需要通过 $f[i-1]$ 的状态便可以轻易求出
在树型背包中,$f[u]$ 的状态需要由各个子树转移过来,设子树的编号为 $son_i$ ,我们发现二者之间不再是简单的线性关系
我们先按照线性背包的角度来考虑树型背包:
如果不选节点 $u$ ,由于本题的限制,所有的子节点都不能选,因此 $f[u][j]=0$
如果选择节点 $u$ ,此时剩余体积为 $j-v[u]$
不难发现,我们可以轻易地通过遍历各个子节点来用 $son_i$ 来表示以子节点为根的子树,也就是数组的第一维,但数组的第二维我们无法表示出来,即以 $son_i$ 为根的子树所对应的体积无法确定
但有一个性质,如果当前以节点 $u$ 为根的子树的体积为 $j$ 的话,所有以 $son_i$ 为根的子树的体积相加一定等于 $j$
基于这一点,由于我们无法确定以节点 $son_i$ 为根的子树的体积为多大,因此我们考虑从 0 开始遍历,最大到 $j$
那么这便是一个分组背包问题了,「组」就是以节点 $son_i$ 为根的每个子树,我们从小到大遍历以 $son_i$ 为根节点的子树的体积
由于每个物品只能选取一个,因此本质上还是 01 背包,所有我们在体积 $j$ 的遍历上还是从后往前
在不同的体积 $j$ 的基础上,我们用 $k$ 表示每个组的体积,此时每个组的最大价值可以表示为 $f[son][k]$ ,那么 $f[u][j]$ 便可以通过 $f[u][j-k]$ 再加上 $f[son][k]$ 转移过来
由于在对以 $son_i$ 为根的子树考虑时,我们一定要选节点 $u$ ,因此我们需要预留一个位置给节点 $u$ ,即 $j$ 的遍历是从 $m-v[u]$ 开始的
当我们遍历完所有的以 $son_i$ 为根的子树时,我们需要将节点 $u$ 的价值加上,即所有体积大于等于 $v[u]$ 的状态均可以从 $f[u][j-v[u]]+w[u]$ 转移而来,小于的全部置 0 (因为如果不能选节点 $u$ ,那么其所有的孩子节点均不能选)
在遍历体积时,我们是从后往前遍历,关于这个我们详细说明一下:
我们 $f[u][j]$ 的定义为:考虑以 $u$ 为根的子树,在背包体积不超过 $j$ 的所有选法
实际上这里是省区了一维,完整写法应该是 $f[u][i][j]$ 的定义为:考虑以 $u$ 为根的子树,对以 $u$ 为根的前 $i$ 个子树进行选择,在背包体积不超过 $j$ 的所有选法
完整代码:
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 110;
int f[N][N];
int h[N], e[N], ne[N], idx;
int v[N], w[N];
int n, m;
void dfs(int u)
{
for(int i = h[u]; ~i; i = ne[i])
{
int son = e[i];
dfs(son);//先对当前子树遍历一次,之后再处理f[u][j],这是因为我们的遍历方式是从下往上遍历的,即后序遍历
for(int j = m - v[u]; j >= 0; j--)//提前预留第u个物品的体积,遍历 考虑范围相同 但 体积不同 下的情况
{
//由于每个物品只能用一次,因此是01背包,从后往前遍历
for(int k = 0; k <= j; k++)//遍历每个子树的体积,不能超过j
{
f[u][j] = max(f[u][j], f[u][j - k] + f[son][k]);//每个子树的体积为k,那么只能从j-k的体积转移过来
}
}
}
for(int i = m; i >= v[u]; i--)//如果体积允许,将节点u加上
f[u][i] = f[u][i - v[u]] + w[u];
for(int i = 0; i < v[u]; i++)//如果体积不允许,那么节点u及其子树的所有物品都不能选,因此价值为0
f[u][i] = 0;
}
void add(int a, int b)
{
e[idx] = b;
ne[idx] = h[a];
h[a] = idx++;
}
int main()
{
cin >> n >> m;
memset(h, -1, sizeof h);
int root = 0;
for(int i = 1; i <= n; i++)
{
int p;
cin >> v[i] >> w[i] >> p;
if(p == -1) root = i;
else add(p, i);
}
dfs(root);
cout << f[root][m] << endl;
return 0;
}