hdu1011（树形背包）

hdu1011 http://acm.hdu.edu.cn/showproblem.php?pid=1011

给定n个洞穴和m个士兵（每个士兵能消灭20个bugs）

然后给定每个洞穴的bugs数量（背包的费用）和brain的数量（背包的价值）

然后给定n-1条边，使得n个洞穴形成一课树

问能取得的brain数量的最大值。

思路：其实就是在树上面进行背包问题的求解，只不过是有依赖的背包（儿子要选，当且仅当父亲也被选）

普通的01背包是这样

for(i=每件物品)

　　for(j=每个容量）

　　　　　dp[i][j] = max(dp[i-1][j],dp[i-1][j-c[i]]+w[i]);

即对于每个物品，求出各个容量的背包对于第i件物品处理完之后的最大值。

那么在树上面进行背包问题，同样要是这样。

第一个循环：

　　但是因为背包是树形的，所以不能用循环来遍历背包，要用dfs来进行遍历

第二个循环：

　　因为是有依赖的背包问题，儿子要选，当且仅当父亲也被选。所以我们要枚举父亲的容量和儿子的容量进行状态转移（即两重循环）

 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <stdlib.h>
 4 #include <algorithm>
 5 #include <iostream>
 6 #include <queue>
 7 #include <stack>
 8 #include <vector>
 9 #include <map>
10 #include <set>
11 #include <string>
12 #include <math.h>
13 using namespace std;
14 typedef long long LL;                   
15 const int INF = 1<<30;
16 const int N = 100+10;
17 struct Cave
18 {
19     int bugs,brain;
20 }cave[N];
21 int dp[N][N];
22 struct Edge
23 {
24     int v,next;
25 }g[N<<1];
26 int head[N],e;
27 
28 /*
29 背包？
30 有依赖的背包
31 容量为m
32 费用为bugs的数量， 价值为brain的数量
33 对于每个洞穴，选或者不选
34 这个洞穴要选，当且仅当父亲被选
35 */
36 bool vis[N];
37 int m;
38 void dfs(int u, int fa)
39 {
40     vis[u] = true;
41     int t = (cave[u].bugs+19)/20;
42     for(int i=t; i<=m; ++i)
43         dp[u][i] = cave[u].brain;
44     for(int i=head[u]; i!=-1; i=g[i].next)
45     {
46         int v = g[i].v;
47         if(vis[v]) continue;
48         dfs(v,u);
49         for(int j=m; j>=t; --j)//必须从后往前推？？？ 由转移方程可以看出，前面的状态依赖于后面的状态，所以要求出后面的状态
50             for(int k=1; k+j<=m; ++k)//所有可能的情况都要枚举，然后求出最大值
51                 dp[u][j+k] = max(dp[u][j+k],dp[u][j]+dp[v][k]);
52         
53         
54     }
55 }
56 void init(int n)
57 {
58     for(e=0; e<=n; ++e)
59     {
60         head[e] = -1;
61         vis[e] = false;
62     }
63     e = 0;
64 }
65 void addEdge(int u, int v)
66 {
67     g[e].v = v;
68     g[e].next = head[u];
69     head[u] = e++;
70 }
71 int main()
72 {
73     int n,i,u,v;
74     while(scanf("%d%d",&n,&m),n!=-1)
75     {
76         init(n);
77         for(i=1; i<=n; ++i)
78             scanf("%d%d",&cave[i].bugs,&cave[i].brain);
79         for(i=1; i<n; ++i)
80         {
81             scanf("%d%d",&u,&v);
82             addEdge(u,v);
83             addEdge(v,u);
84         }
85         if(m==0)
86         {
87             puts("0");
88             continue;
89         }    
90         memset(dp,0,sizeof(dp));
91         dfs(1,-1);
92         printf("%d
",dp[1][m]);
93     }
94     return 0;
95 }

View Code

样例：