POJ 1561 - The more, The Better

POJ 1561 - The more, The Better

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

https://cloud.tencent.com/developer/article/1108936

题意：有n个城堡形成一棵树，你只能攻打m个城堡，每个城堡里都有相应的宝物，要攻克这些城堡必须先攻克其他某一个特定的城堡，就是先攻克根，才可以往下攻击子树，问可以获得最大的宝物。 思路：这道题目和前面不同的是，有两个限制条件，一个是必学攻克父节点才能去攻打子节点，另一个是只能攻克m个城堡。这里可以看出树形dp和依赖背包是不是有一点差不多。其实解决依赖背包问题，就是用树形dp的思路，先解决子树的最优解，然后才能得到根的最优解。过程是从下往上的，而树的DFS就是先搜索到叶子节点，然后逐层往上，不断更新结点的最优值，最终保证根节点的值是最优的。

http://www.cppblog.com/y346491470/articles/162458.html
【题解】：经典的树dp+分组背包。
               由于本题不是一个真正意义上的树，而是一个树林，可增加一个新结点0连向各个树根，转换成一棵树。
               设dp[i][j]表示以i为根的子树，取j个结点（包括i本身）所得的最大宝藏。
               转移方程：
                     dp[i][j] = max(dp[i1][j1] + dp[i2][j2] + dp[i3][j3] + …… + dp[in][jn]) + val[i];
                                 其中i1,i2……in为i的儿子 且 j1 + j2 + j3 + …… + jn = j - 1;
               对于i的每个儿子，都有很多不同价值、不同代价的子树，我们可以将他们泛化成物品，这样就把问题转换成背包问题。
               我们把i的每个儿子的子树所形成的不同物品归为一组，显然对于每一组物品，我们要么取一个，要么不取，既不能取两个或两个以上。[认真思考]
               这样就成为经典的分组背包问题，具体可以参考背包九讲。
               由于我们新加了根，所以 ans = dp[0][m+1];

https://blog.csdn.net/qq_34374664/article/details/56279988
这题目可以看成是一个森林，对于需要攻占的城堡作为根节点，攻占了这个根节点以后可以立即攻占的城堡作为它的孩子，那么这就变成了树形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]）典型的依赖背包



给定一个森林，每个点有权值，如果要选子节点，要保证父节点已经选择，问选m个节点最大的权值和。
用0作为虚结点，树上背包，dp[i][j]为到i节点为止，选了j个物品的最大权值和
对除0外的点
多么明显 有依赖性的 01背包！这个依赖点是0 

设1个0节点，本身价值是0，dp[i][j]表示第i个节点，取了j个节点后的价值。由于先取父亲才能取儿子，所以要从dp[i][1] 开始转移。把子节点的状态转移到父亲节点。

由于和分组背包1样，子节点不能重复更新父亲节点，所之外层循环父节点状态，从大到小，内层循环子节点状态。

http://blog.csdn.net/woshi250hua/article/details/7637847

和Poj1155、1947一样，都是在树形结构上进行分组背包处理。本题的依赖关系可以理解成树边，到达子节点必须先经过父节点，本质是一样的，这样可以建立起一个森林，如果为每棵树的添加一个公共父节点0那就成了一棵树了，这是个实用性很强的小技巧。建立起一棵树就开始如何进行dp，如何从子节点获取信息。

    一个子节点就可以返回m个状态，每个状态表示容量为j（j<=m)时选最多的宝物，而一个子节点中只可以选择一个状态进行转移，每个节点有若干个子节点，问题就转换为分组背包，几个子节点就是几个分组背包，体积是选几个地点，价值是宝物价值。

     状态转移方程: dp[v][1] = Money[v]; (v为叶子节点)
                          dp[v][j] = max(dp[v][j],dp[v][j-i] + dp[k][i] );(v为非叶子节点,j表示用户个数,i为容量，k为v的子节点,)
    算法复杂度O(sum(num[i],num[s])) (num[i]为某个节点的叶子子孙个数，num[s]为i的子节点的叶子子孙个数)

    本题加了个剪枝，每次转移时不必都从最大容量m开始，而可以把当前可能转移的最大容量算出来进行转移，最大容量就是子节点个数，速度快了10几倍。

1. struct node {  
2.   
3.     int v;  
4.     node *next;  
5. }*head[MAX],tree[MAX];  
6. int n,m,money[MAX]; //root表示输入时是否与根相连  
7. int ptr,dp[MAX][MAX];  
8.   
9.   
10. void Initial() {  
11.       
12.     ptr = 1;  
13.     memset(dp,0,sizeof(dp));  
14.     memset(head,NULL,sizeof(head));  
15. }  
16. void AddEdge(int fa,int son) {  
17.   
18.     tree[ptr].v = son;  
19.     tree[ptr].next = head[fa];  
20.     head[fa] = &tree[ptr++];  
21. }  
22. int Tree_DP(int v) {  
23.   
24.     int i,j,k,tot = 1;  
25.     node *p = head[v];  
26.   
27.       
28.     while (p != NULL) {  
29.   
30.         tot += Tree_DP(p->v);  
31.         int tp = tot < m ? tot : m;      //加个剪枝，这个到目前为止能到达最大容量  
32.         for (j = tp; j >= 1; --j)   //分组背包  
33.             for (i = 1; i <= j; ++i)  
34.                 dp[v][j] = max(dp[v][j],dp[p->v][i]+dp[v][j-i]);  
35.         p = p->next;  
36.     }  
37.   
38.   
39.     if (v != 0) {  
40.   
41.         for (j = m; j >= 1; --j)  
42.             dp[v][j] = dp[v][j-1] + money[v];   //必选当前节点自己  
43.     }  
44.     return tot;  
45. }  
46.   
47.   
48. int main()  
49. {  
50.     int i,j,k,a,b;  
51.   
52.   
53.     while (scanf("%d%d",&n,&m),n+m) {  
54.   
55.         Initial();  
56.         for (i = 1; i <= n; ++i) {  
57.   
58.             scanf("%d%d",&a,&b);  
59.             money[i] = b;  
60.             AddEdge(a,i);  
61.         }  
62.   
63.   
64.         Tree_DP(0);  
65.         printf("%d\n",dp[0][m]);  
66.     }  
67. } 

Read full article from Problem - 1561