01背包问题+树形DP
对于u这个节点,如果以方案来划分子节点,就退化成了爆搜
但是以体积来枚举子节点,因为体积不大,所以是一个很经典的优化
然后等于对子节点做对于体积的01背包
状态定义 $f[i][j]$ :考虑到节点 $i$ 且总使用体积为 $j$ 的最大价值
状态转移:枚举所有分配给子树的体积 $[m-v[i],0]\(倒序)$
$f[u][j]=max(f[u][j],f[u][j-k]+f[next][k])$
最后分类该节点本身:
物品选上$i$: $f[u][i]=f[u][i-v[u]]+w[u]$,$i\in{[m,v[u]]}$
不选上 $i$ :$f[u][i]=0$,$i\in{[0,v[u])}$
对于枚举方案数的情况,可以使用状态压缩来枚举所有信息。
参考金明的预算方案
枚举体积的时间复杂度 $O(N\*V\*V)$
枚举方案的时间复杂度 $O(N * M * 2^k)$
体积小枚举体积,如果子树的分枝都很小,那么就可以枚举方案。
如果权在边上,参考二叉苹果树
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=110*110;
int n,m;
int h[N],e[N],en[N],idx;
int v[N],w[N];
int f[N][N];
void add(int a,int b)
{
e[idx]=b,en[idx]=h[a],h[a]=idx++;
}
void dfs(int u)
{
for(int i=h[u];i!=-1;i=en[i]){
int next=e[i];
dfs(next);
for(int j=m-v[u];j>=0;j--)
for(int k=0;k<=j;k++)
f[u][j]=max(f[u][j],f[u][j-k]+f[next][k]);
}
for(int i=m;i>=v[u];i--) f[u][i]=f[u][i-v[u]]+w[u];
for(int i=0;i<v[u];i++) f[u][i]=0;
}
int main()
{
memset(h,-1,sizeof h);
cin>>n>>m;
int root;
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;
}