[Acwing] 10. 有依赖的背包问题 树形DP+分组背包

前言

树形DP+分组背包的组合拳 传送门 :

思路

集合划分 : 以子树划分 ? 以子树内的体积划分 ?

• 以子树划分 显然 2 k 2^k 2k 最快情况下,显然是不太理想的
• 以子树内的体积划分,那么就可以划分成 0 − m 0 -m 0−m 的划分

因此我们可以把每一个子树看成一个组,因此问题就转换成为分组背包的问题

因此状态表示就是 : f [ u ] [ k ] f[u][k] f[u][k] 表示以 u u u为根节点的子树中选,体积不超过 k k k的最大价值

因此根据AcWing285.上司的舞会 我们就可以得知

状态转移方程为 :

f [ u ] [ k ] = f [ u ] [ j − k ] + f [ s o n ] [ k ] f[u][k] = f[u][j-k]+f[son][k] f[u][k]=f[u][j−k]+f[son][k]

剩余背包的最大价值和加入子节点的最大价值

CODE

const int N  = 110;
int f[N][N];
//f[u][j] 表示根节点为u 体积为j的所有选法中的最大价值
vector g[N];

int v[N],w[N],p[N];
int n,m;

void dfs(int u)
{
	//节点必须寻上 f[u][v[u]~m] = w[u]
	for(int j  = v[u];j=0;j--)
			for(int k = 0;k=v[u])
			f[u][j] =  max(f[u][j],f[u][j-k]+f[son][k]);
	}
	
}
void solve()
{
	cin>>n>>m;
	int root = 0 ;
	
	for(int i=1;i>v[i]>>w[i]>>p[i];
		if(p[i] == -1)
		root = i ;
		else
		g[p[i]].push_back(i);
	//因为依赖关系 不是双向边？ 
	}	
	dfs(root);
	cout