HDU 1561 The more, The Better 超详细题解(树形DP + 依赖背包)

前端之家收集整理的这篇文章主要介绍了HDU 1561 The more, The Better 超详细题解(树形DP + 依赖背包)前端之家小编觉得挺不错的,现在分享给大家,也给大家做个参考。


The more,The Better

Time Limit: 6000/2000 MS (Java/Others)Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 7970Accepted Submission(s): 4673


Problem Description
ACboy很喜欢玩一种战略游戏,在一个地图上,有N座城堡,每座城堡都有一定的宝物,在每次游戏中ACboy允许攻克M个城堡并获得里面的宝物。但由于地理位置原因,有些城堡不能直接攻克,要攻克这些城堡必须先攻克其他某一个特定的城堡。你能帮ACboy算出要获得尽量多的宝物应该攻克哪M个城堡吗?

Input
每个测试实例首先包括2个整数,N,M.(1 <= M <= N <= 200);在接下来的N行里,每行包括2个整数,a,b. 在第 i 行,a 代表要攻克第 i 个城堡必须先攻克第 a 个城堡,如果 a = 0 则代表可以直接攻克第 i 个城堡。b 代表第 i 个城堡的宝物数量,b >= 0。当N = 0,M = 0输入结束。

Output
对于每个测试实例,输出一个整数,代表ACboy攻克M个城堡所获得的最多宝物的数量

Sample Input
  
  
3 2 0 1 0 2 0 3 7 4 2 2 0 1 0 4 2 1 7 1 7 6 2 2 0 0

Sample Output
  
  
5 13

先贴网上看到的两个很好的题解:

题解一:

这题目可以看成是一个森林,对于需要攻占的城堡作为根节点,攻占了这个根节点以后可以立即攻占的城堡作为它的孩子,那么这就变成了树形DP了,因为这有可能是一个森林,所以我们将一开始就可以攻占的城堡作为0号节点的孩子,这样就可以将一个森林转化成一棵树了,然后对于每一个节点,因为它的孩子的组合有多种,同时孩子的孩子也会影响它们,所以这个问题可以转化为有依附的背包问题,每一个节点作为原件,它的孩子们作为附件,然后对孩子们跑一遍01背包,这样就可以用孩子的属性求出整棵子树的属性,然后一层一层地想向上推,最终就可以得到结果了。
  状态转移方程:dp[r][j]=max{dp[r][j],dp[r][j-k]+dp[ver[r][i]][k]} 其中r代表以r为根节点的子树;j为容量为j的背包,这里的意思是以r为根节点的子树一共取j个节点;k的意思是从r的第i个孩子的子树那里挑k个节点,ver[r][i]代表r的第i个孩子的标号;dp[r][j]的意思是从以r为根的子树取j个节点的最大价值是多少。
  代码那里有一个地方需要注意的,就是k不可以等于j,因为j是从一棵子树取的节点数,只要j>0,那么j里面一定要包含根节点,k==j的意思就是在不取根节点的情况下在子树上取j个节点,这不合题意。

题解二:

这题其实就是经典的《选课》问题
状态 dp[i][j] 为以 i 为根节点,选出 j 个节点的最大价值(包括 i 这个节点)
转移方程:dp[i][j]=max(dp[i1][j1]+dp[i2][j2]+....+dp[ik][jk])+a[i] j1+j2+...+jk=j-1
由于这个题目上的树并非一棵树而是一个森林,因此我们通过把根设为0使其变成真正意义上的树
那么答案:dp[0][m+1]
看到这个转移方程可能一时难以下手,因为你当前的状态转移是要搞定子节点的各个分支上的情况的
即子节点上各个分支分别取了多少个物品,才能使得决策最优
而对于这个问题,我们可以发现与经典的背包问题存在着相似性,这里的 j 其实就是背包的容量
因此对于这个子问题,我们可以用背包来取最优
记 dp0[i][j] 为以 i 为根节点,它的分支中取出 j 个节点的最大价值
那么转移方程就是经典的背包
dp0[i][j+k]=max{dp0[i][j+k],dp0[i][j]+dp[son[i]][k]}
即我们在一个分支中最优的取出 k 个物品后,从 j 转移到了 j+k

从这里我们也可以看出
本题的DP状态和子问题背包的DP状态其实两个是紧密相连的
两者的区别也仅仅在于本题的DP状态对于以 i 为根节点的子节点情况,它是包括 i 这个根节点本身的
而背包的状态则是不包括在内的,而就是这样的区别导致它们在具体转移的时候方程是很不一样的
实现的一些细节:
1:图用邻接表来存储,偷懒的方式是用一个 二维 vector
2:树形DP中表示某个点没有访问应该把它设置成 -1
3:用记忆化搜索实现比较容易而且高效,因为记忆化搜索只是计算了那些我们需要的状态,而递推来搞的话,往往把所有的状态都给算出来了

做题感悟:

第一次做树上背包。。想要很清楚的学会这个题,首先要了解什么是依赖背包,树上背包是一个很经典的依赖背包,依赖背包指的是在取某个点的之前,必须先取某个点,这与树不谋而合,你要到子节点必须要先经过父节点。树上背包一般是有个“代价”限制,每个节点都有一些“代价”跟“价值”,问你怎样才能找到在限制内获得最大价值。。对于每个节点来说,他是从所有儿子节点的不同组合里找到一个最优解,这些儿子节点的“代价和”sum,是总的代价和-父节点的代价,这个题每个节点的代价是1,所以很好做。。。但是如果代价不是1而且都不相同,我想不出来怎么做。。等着在学一下吧。。 这个题就是对节点的儿子进行一下背包,从所有儿子里挑出最优方案,这里的dp[][]数组是二维的,其中第一维是代表节点,第二维才是背包(相当于背包变成一维模式),从每个节点的儿子依次取出0-v-1(根节点必须选)个点,利用背包更新根节点的数组,这里就相当于分组背包了,引自背包九讲的一段话“

这个问题变成了每组物品有若干种策略:是选择本组的某一件,还是一件都不选。也就是说设f[k][v]表示前k组物品花费费用v能取得的最大权值,则有:

f[k][v]=max{f[k-1][v],f[k-1][v-c[i]]+w[i]|物品i属于第k}

使用一维数组的伪代码如下:

for所有的组k

for v=V..0

for所有的i属于组k

f[v]=max{f[v],f[v-c[i]]+w[i]}

注意这里的三层循环的顺序,甚至在本文的beta版中我自己都写错了。for v=V..0”这一层循环必须在“for所有的i属于组k”之外。这样才能保证每一组内的物品最多只有一个会被添加到背包中。

第一个for是枚举当前节点的几个儿子,第二个for就是在这枚举背包大小了,第三个for枚举这个儿子里的情况(每种情况都已经知道了,即主件i附件集合先进行一次01背包,得到费用依次为0..V-c[i]所有这些值时相应的最大价值f'[0..V-c[i]]。那么这个主件及它的附件集合相当于V-c[i]+1个物品的物品组,其中费用为c[i]+k的物品的价值为f'[k]+w[i])典型的依赖背包

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
const int maxn = 205;
vector<int> p[maxn];
int dp[maxn][maxn],val[maxn],n,m;
void dfs(int x,int w)
{
    dp[x][1] = val[x]; //选一个肯定选自己,注意区别一般的依赖背包,这里的dp[x][]还没有回溯到,正在根据子节点提供的信息算dp[x][],所以不能直接一个for,dp[x][] = dp[i-1][j-c[i]]
    for(int i = 0; i < p[x].size(); i++) //这一块就是分组背包了,这里是一共i组
    {
        int to = p[x][i];
        dfs(to,w-1);  //每用掉一个节点,后面“代价总和”就要少一个节点,否则后面可能选出来x个点,但是它最多就能w歌点,这样就不对了。。要不断更新最大值,因为有依赖关系
        for(int v = w; v > 1; v--)  //这里是>1,因为要扣掉父亲节点。 这里是枚举v
        {
            for(int k = 0; k < v; k++) //每个儿子的“代价”是1  这里是美剧每一组的所有k,这种顺序是因为每组只能选一种情况,这样保证了这个条件,每个k对应的价值都已经回溯出来了
            {
                dp[x][v] = max(dp[x][v],dp[x][v-k]+dp[to][k]);
            }
        }
    }
}
int main()
{
    while(~scanf("%d%d",&n,&m),m+n)
    {
        int a,b;
        memset(dp,sizeof(dp));
        memset(val,sizeof(val));
        for(int i = 0; i <= maxn; i++) p[i].clear();
        for(int i = 1;i <= n; i++)
        {
            scanf("%d%d",&a,&b);
            p[a].push_back(i);
            val[i] = b;
        }
        m++;
        dfs(0,m);
        printf("%d\n",dp[0][m]);
    }
    return 0;
}

这题经常跟一般的依赖背包比较下:http://www.jb51.cc/article/p-dekygbko-bqn.html

原文链接:https://www.f2er.com/javaschema/283303.html

猜你在找的设计模式相关文章