我是靠谱客的博主 瘦瘦宝贝,最近开发中收集的这篇文章主要介绍树形背包总结概念一、基于dfs合并:二、dfs序上dp:例题1例题2例题3总结下:,觉得挺不错的,现在分享给大家,希望可以做个参考。

概述

目录

  • 概念
  • 一、基于dfs合并:
    • 1、物品大小为1,没有限制:
      • (伪)代码:
    • 2、有物品大小:
    • 3、物品大小为1,有k的限制。
      • (伪)代码:
      • 复杂度证明:
  • 二、dfs序上dp:
    • 代码
    • 时间复杂度分析
  • 例题1
  • 例题2
  • 例题3
  • 总结下:

概念

树形背包,就是说,在树上选一个包含根的连通块,或背包存在依赖关系(选父才能选子),或者需要知道每个点的子树中选了多少……
通常,我们有两种方法:

一、基于dfs合并:

我们设(dp(i,j))表示在i的子节点中选j个的状态。
在转移时,先dfs子节点,然后依次把子节点合并,每次合并2个。
即枚举(a,b),用(dp(i,a))(dp(son,b))组合为(f(a+b)),每次合并后,把f赋给dp。

下面分析时间复杂度:

1、物品大小为1,没有限制:

(伪)代码:

void Tree_Dp(int p)
{
size[p]=1;
each(x,son[p])
{
Tree_Dp(x);
for(int i=0;i<=size[p];++i)
for(int j=0;j<=size[x];++j)
update dp[p][i+j];
size[p]+=size[x];
}
}

时间复杂度为(O(n^2))
考虑那个二重循环,可以看做分别枚举两棵子树的每个点。可以发现,点对((u,v)),只会在(Tree_Dp(lca(u,v)))处被考虑到,所以复杂度是(O(n^2))

2、有物品大小:

这个复杂度我也不清楚,可以卡到(O(n^3)),但是,在数据随机时是能跑过8000,1s的。

3、物品大小为1,有k的限制。

(伪)代码:

void dfs(int u, int fu) {
int si = 0;
for (int i = fr[u]; i != -1; i = ne[i]) {
if (v[i] != fu)
dfs(v[i], u);
}
for (int i = fr[u]; i != -1; i = ne[i]) {
if (v[i] == fu) continue;
int rt = sz[v[i]];
for (int a = 0; a <= min(si, k); a++) {
for (int b = 0; b <= min(rt, k - a); b++) {
//转移dp
}
}
si += rt;
sz[u] = si + 1;
}

这个算法,最初觉得是(O(nk^2))的,实际上是(O(nk))的。

复杂度证明:

  1. 根据正常树形背包的复杂度(O(n^2)),小于等于k的最多产生(n/k*k^2)的复杂度。
  2. 大于k与大于k的合并一次,被合并的就增加k,最多n/k次,最多产生(n/k*k^2)的复杂度。
  3. 大于k的与小于等于k的合并时,每个小于等于k的最多被合并一次,所以是(n*s_1+n*s_2+...+n*s_m),也是(nk)

还有一种理解:

把树按照dfs序变为序列。
然后,在子树中枚举取x个,可以理解为取dfs序的前(后)x个。
而合并时,认为一棵子树取后x个,另一棵取前y个。((x+yleq k))。这可以合并为长x+y的区间。
这其实就是长度不大于k的子串,最多有nk个。
但是,因为有取0个的情况,所以实际做题时,大约有2的常数。但那个常数就忽略了可以。

二、dfs序上dp:

按照dfs序考虑:
我们设(dp(i,j))表示考虑到第i个,剩余容量为j的状态:
有两种转移:
1、不选i,那么i的子树都不能选,转移到(dp(i+Size_i,j))
2、选i,那么按照dfs序考虑下一个,转移到(dp(i+1,j-w)+v)
正确性显然。

代码

(不是我的)

void dfs(int u)
{
int tmp=tot;
for(int i=head[u];i;i=indexx[i].next)
{
int v=indexx[i].to;
dfs(v);
}
cost[++tot]=temp[u];
f[tot]=tmp;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&v[i],&p[i],&q[i]);
temp[i]=banana(v[i],v[i]*p[i]);
init(q[i],i);
}
dfs(0);
for(int i=1;i<=m;i++)
{
for(int j=0;j<=n;j++)
{
if(j>=cost[i].v)
dp[i][j]=max(dp[f[i]][j],dp[i-1][j-cost[i].v]+cost[i].w);
else
dp[i][j]=dp[f[i]][j];//fi就是i-size(i)
}
}
printf("%dn",dp[m][n]);
}

时间复杂度分析

这个比较显然,n个点,m的容量限制(没有则m=n),状态有(nm)个,转移代价为(O(1)),复杂度为(O(nm))
而且,这种方法更好些,且常数更小。

例题1


题目描述

金明今天很开心,家里购置的新房就要领钥匙了,新房里有一间金明自己与用的很宽敞的房间。更让他高兴的是,妈妈昨天对他说:“你的房间需要购买哪些物品,怎么布置,你说了算,只要丌超过 N 元钱就行”。今天一早,金明就开始做预算了,他把想买的物品分为两类:主件不附件,附件是从属于某个件的,下表就是一些主件不附件的例子:

主件 附件

电脑 打印机,扫描仪

书柜 图书

书桌 台灯,文具

工作椅 无

如果要买归类为附件的物品,必须先买该附件所属的件。每个主件可以有很多个附件。附件可能有从属于自己的附件。金明想买的东西很多,肯定会超过妈妈限定的 N 元。于是,他把每件物品规定了一个重要度,分为 5 等:用整数 1−5 表示,第 5 等最重要。他还从因特网上查到了每件物品的价格(都是在10 元以内)。他希望在不超过 N 元(可以等于 N 元)的前提下,使每件物品的价格不重要度的乘积的总和最大。 设第 j 件物品的价格为 v[j] ,重要度为 w[j] ,共选中了 k 件物品,编号依次为 j1,j2,…,jk,则所求的总和为: v[j1]×w[j1]+v[j2]×w[j2]+…+v[jk]×w[jk] 请你帮助金明设计一个满足要求的购物单。
输入格式

第 1 行,为两个正整数,用一个空格隔开:

N,m (其中 N(<8000) 表示总钱数, m(< 8000) 为希望购买物品的个数。) 从第 2 行到第 m+1 行,第 j 行给出了编号为 j−1的物品的基本数据,每行有 3 个非负整数::v,p,q(其中 v 表示该物品的价格( v< 10),p表示该物品的重要度( 1−5 ), q 表示该物品是主件还是附件。如果 q=0,表示该物品为主件,如果 q>0 ,表示该物品为附件, q 是所属件的编号(q< j-1))
输出格式

一个正整数,为丌超过总钱数的物品的价格不重要度乘积的总和的最大值。


这个,是显然的树型背包。
如果用方法1,则由于物品大小的影响,可以卡到(O(nm^2))
但是,方法二就是(O(nm))的,很快,还好写。

1752467-20190914201547410-198935068.png

(差距很大)。

例题2

[JSOI2018]潜入行动
这题,由于我要知道父子关系的信息(例如:父节点是否选择等),所以方法二便不能使用。

例题3

[SDOI2017]苹果树
这题有些像例1,只不过物品有多个,转成dfs序后,单调队列优化即可,复杂度(O(nk))。如果方法1至少要(O(nk^2))

总结下:

方法一:
可以知道每个点的确切情况,可以与普通的树型dp结合使用(因为毕竟是在树上)。
但是,复杂度较高(因为合并背包很慢)。

方法二:
复杂度较低(因为不需要合并背包,相当于依次添加)。
但是,不能知道每个点的确切情况(因为是在序列上),有些题不能使用。

转载于:https://www.cnblogs.com/lnzwz/p/11519977.html

最后

以上就是瘦瘦宝贝为你收集整理的树形背包总结概念一、基于dfs合并:二、dfs序上dp:例题1例题2例题3总结下:的全部内容,希望文章能够帮你解决树形背包总结概念一、基于dfs合并:二、dfs序上dp:例题1例题2例题3总结下:所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错,欢迎将靠谱客网站推荐给程序员好友。

本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
点赞(51)

评论列表共有 0 条评论

立即
投稿
返回
顶部