为什么树上背包问题都是01背包呢?
  • 板块灌水区
  • 楼主asdfo123
  • 当前回复3
  • 已保存回复3
  • 发布时间2020/10/14 17:09
  • 上次更新2023/11/5 10:47:14
查看原帖
为什么树上背包问题都是01背包呢?
272945
asdfo123楼主2020/10/14 17:09

最近复习到p2014选课,p2015二叉苹果树等题,都说是01背包,请问内在逻辑是什么啊?

还有蓝书上说实际上树上背包是一种分组背包,对于枚举的体积j里面的k怎么理解呢?


void dp(int now)
{
	for(int i = head[now];i;i = e[i].nxt)
	{
		int go = e[i].to;
		dp(go);
		for(int j = m+1;j>=1;j--)
		{
			for(int k = 0;k < j;k++)
			{
				f[now][j] = max(f[now][j],f[go][k]+f[now][j-k]);
			}
		}
	}
}

2020/10/14 17:09
加载中...