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来进行遍历
第二个循环：
因为是有依赖的背包问题，儿子要选，当且仅当父亲也被选。所以我们要枚举父亲的容量和儿子的容量进行状态转移（即两重循环）
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <algorithm>
#include <iostream>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <string>
#include <math.h>
using namespace std;
typedef long long LL;
const int INF = <<;
const int N = +;
struct Cave
{
int bugs,brain;
}cave[N];
int dp[N][N];
struct Edge
{
int v,next;
}g[N<<];
int head[N],e; /*
背包？
有依赖的背包
容量为m
费用为bugs的数量， 价值为brain的数量
对于每个洞穴，选或者不选
这个洞穴要选，当且仅当父亲被选
*/
bool vis[N];
int m;
void dfs(int u, int fa)
{
vis[u] = true;
int t = (cave[u].bugs+)/;
for(int i=t; i<=m; ++i)
dp[u][i] = cave[u].brain;
for(int i=head[u]; i!=-; i=g[i].next)
{
int v = g[i].v;
if(vis[v]) continue;
dfs(v,u);
for(int j=m; j>=t; --j)//必须从后往前推？？？ 由转移方程可以看出，前面的状态依赖于后面的状态，所以要求出后面的状态
for(int k=; k+j<=m; ++k)//所有可能的情况都要枚举，然后求出最大值
dp[u][j+k] = max(dp[u][j+k],dp[u][j]+dp[v][k]); }
}
void init(int n)
{
for(e=; e<=n; ++e)
{
head[e] = -;
vis[e] = false;
}
e = ;
}
void addEdge(int u, int v)
{
g[e].v = v;
g[e].next = head[u];
head[u] = e++;
}
int main()
{
int n,i,u,v;
while(scanf("%d%d",&n,&m),n!=-)
{
init(n);
for(i=; i<=n; ++i)
scanf("%d%d",&cave[i].bugs,&cave[i].brain);
for(i=; i<n; ++i)
{
scanf("%d%d",&u,&v);
addEdge(u,v);
addEdge(v,u);
}
if(m==)
{
puts("");
continue;
}
memset(dp,,sizeof(dp));
dfs(,-);
printf("%d\n",dp[][m]);
}
return ;
}
样例：