有依赖的背包问题模板题
本质是树形dp + 分组背包问题
状态表示
f[u][j]
:表示根节点为u,体积为j的所有选法中的最大价值
状态计算
- 集合划分:按照体积进行划分
(指的是子树之间可以组合成的所有体积)
**集合划分用了一个技巧**
**朴素的集合划分**:按照不同子节点进行划分,最坏情况下的时间复杂度为2^k
**按照子节点可以组合成的所有可能的体积来进行划分**:假设体积为m,那么只有0 ~ m种选择,时间复杂度大大降低了
- 每个子树看作一个组,且组内的选择是唯一
(只能选择一种可能的体积)
,那么求每棵子树就相当于求分组背包问题 - 计算每个节点的状态的过程为
树形dp
参考 AcWing 285. 没有上司的舞会
题意:
条件:如果选择物品5,则必须选择物品1和2。这是因为2是5的父节点,1是2的父节点。,
通过这个条件,我们直到要想计算当前节点u的子树的最大值,那么就表示当前节点u必须要选上
树形dp + 分组背包
#include<algorithm>
#include<iostream>
#include<cstring>
using namespace std;
const int N = 110;
int f[N][N];
//f[u][j]表示根节点为u,体积为j的所有选法中的最大价值
int h[N]; //邻接表中每条链的表头
int e[N],ne[N]; //e[]记录当前节点的编号,ne[]记录当前节点的下一个节点
int idx; //表示当前节点的指针
int v[N],w[N],p[N]; //分别表示第i个物品的体积,价值,依赖(父)节点
int n,m; //n表示物品个数,m表示背包容量
void add(int a,int b){
e[idx] = b;
ne[idx] = h[a];
h[a] = idx++;
}
void dfs(int u){
//因为u节点必须选上,所以先初始化,f[u][v[u] ~ m] = w[u];
for(int j = v[u];j <= m;++j) f[u][j] = w[u];
//树形dp模板
for(int i = h[u];i != -1;i = ne[i]){ //枚举子节点
int son = e[i];
//递归到最底下,再用最底层的结果计算
dfs(son);
//分组背包(按体积进行分组)
for(int j = m;j >= 0;--j){ //枚举背包体积(从大到小枚举,主要是为了满足k<=j - v[u]的条件)
for(int k = 0;k <= j - v[u];++k){ //枚举组内选择,只能选择一个(预留出v[u]的空间)
//背包容量至少要为v[u],因为要预留出u节点的位置
if(j >= v[u]) f[u][j] = max(f[u][j],f[u][j - k] + f[son][k]);
}
}
}
}
int main(){
int root;
cin >> n >> m;
memset(h,-1,sizeof h);
for(int i = 1;i <= n;++i){
cin >> v[i] >> w[i] >> p[i]; //分别表示物品的体积、价值和依赖的物品编号
if(p[i] == -1){
root = i;
}else{
add(p[i],i); //p是i的父节点
}
}
dfs(root);
cout << f[root][m] << endl;
return 0;
}