题意：你作为星河站队的leader，手下有m个trooper；现在让你去攻占一个基地：有n个洞穴组成，入口是洞穴1，洞穴之间用n-1条边链接，每个洞穴里面包括x个bugs,和他们的brains，你的每个trooper可以消灭20个bugs；问你最多可以得到多少个brains。
需要注意的是：你没做过的叶子必须要留人，也就是说就算某个地方的bug是0个，你也要牌一个trooper过去。
写这个题目的时候，开始用的是以前的依赖背包的思想，而且代码也是按照依赖背包写的，写的比较长，也比较繁琐，主要思路是：
因为入口是1，所以从1开始，设P=1，P是访问到的节点编号，设dp[i]表示i是需要的trooper数量，当作价格，dp[i]是得到的brains数量，当作价值：
1、遍历P的所有孩子，如果P的孩子i还有孩子，P=i，转到1，遍历完以后，如果所有的孩子都没有子孩子，转到2，否组转到3；
2、对所有的孩子进行01背包：初始化dp都是P的价值，然后进行01背包，然后把dp[i]对应的值都后移P的价格。因为如果想到到达P的孩子，必须到达P。然后回溯到上一层1，继续遍历P；
3、由于P的有些孩子还有孩子，那么处理的时候就要按照不同的情况进行01和分组背包处理，对于没有孩子的孩子，按照01背包处理，对于有孩子的孩子，对其进行分组背包的处理，然后回溯到上一层1继续遍历P；
代码如下：
/*#include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <vector> using namespace std; #define N 110 int num,total_price,dp[N][N]; struct Room{ int price,value; }room[N]; bool visited[N]; vector <int> connected[N]; void init() { int i,x,y; memset(dp,sizeof(dp)); memset(visited,true,sizeof(visited)); for(i=0;i<=num;i++) connected[i].clear(); for(i=1;i<=num;i++) { scanf("%d%d",&room[i].price,&room[i].value); room[i].price=ceil(room[i].price/20.0); if(room[i].price>total_price) visited[i]=false; } for(i=1;i<num;i++) { scanf("%d%d",&x,&y); connected[x].push_back(y); connected[y].push_back(x); } } void dfs(int key) { visited[key]=false; int i,j,k; for(i=room[key].price;i<=total_price;i++) dp[key][i]=room[key].value; for(i=0;i<(int)connected[key].size();i++) { int s=connected[key][i]; if(!visited[s]) continue; dfs(s); for(j=total_price;j>=room[key].price;j--) { for(k=1;k+j<=total_price;k++) { if(dp[s][k]) dp[key][j+k]=max(dp[key][j+k],dp[key][j]+dp[s][k]); } } } } int main() { while(cin>>num>>total_price&&((num+1)||(total_price+1))) { init(); if(!total_price) { cout<<"0"<<endl; continue; } dfs(1); cout<<dp[1][total_price]<<endl; } }*/ #include <cstdio> #include <cstring> #include <iostream> #include <cmath> #include <list> using namespace std; #define N 105 struct Room{ int price,value; }room[N*N]; bool map[N][N],de_room[N],de_map[N]; list <int>tree[N]; int num,ans,num_i,num_j; void update(int key) { de_room[key]=false; int i; tree[key].clear(); for(i=1;i<=num;i++) { if(map[key][i]&&de_room[i]) { tree[key].push_back(i); de_room[i]=false; } } list <int>::iterator p=tree[key].begin(); while(p!=tree[key].end()) { update(*(p++)); } } void fun(int key) { int dp[N],i,k; memset(dp,sizeof(dp)); list <int> ::iterator p=tree[key].begin(); while(p!=tree[key].end()) { if(tree[*p].empty()) { k=0; if(room[*p].price==0) k=1; for(i=total_price;i>=room[*p].price+k;i--) { dp[i]=max(dp[i],dp[i-room[*p].price-k]+room[*p].value); } } else { fun(*p); for(i=total_price;i>=0;i--) { list <int> ::iterator q=tree[*p].begin(); while(q!=tree[*p].end()) { if(i>=room[*q].price) dp[i]=max(dp[i],dp[i-room[*q].price]+room[*q].value); q++; } } tree[*p].clear(); } p++; } tree[key].clear(); if(key==num_i) { if(total_price-room[num_i].price>=0) ans=max(ans,dp[total_price-room[num_i].price]+room[num_i].value); return ; } for(i=total_price;i>=0;i--) { if(dp[i]<=0) { room[++num_j].price=room[key].price; if(room[key].price==0) room[num_j].price+=1; room[num_j].value=room[key].value; tree[key].push_back(num_j); break; } if(i+room[key].price<=total_price) { room[++num_j].price=i+room[key].price; room[num_j].value=dp[i]+room[key].value; tree[key].push_back(num_j); } } } int main() { while(scanf("%d%d",&num,&total_price)) { ans=0; if(num==-1&&total_price==-1) return 0; memset(de_map,sizeof(de_map)); memset(map,false,sizeof(map)); int i,y; for(i=1;i<=num;i++) { scanf("%d%d",&room[i].value); room[i].price=ceil(room[i].price/20.0); if(room[i].price>total_price) de_map[i]=false; } for(i=1;i<num;i++) { scanf("%d%d",&y); if(de_map[x]&&de_map[y]) map[x][y]=map[y][x]=true; } if(total_price==0) { cout<<"0"<<endl; continue; } memset(de_room,sizeof(de_room)); num_i=1;num_j=num; update(1); fun(1); cout<<ans<<endl; } }
上边的思想和代码都比较繁琐，后来在网上参考了一些代码，用的其实还是依赖背包的思想，只是方法变了。
代码如下：
#include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <vector> using namespace std; #define N 110 int num,&room[i].value); room[i].price=ceil(room[i].price/20.0); if(room[i].price>total_price) visited[i]=false;//小小的优化，就是如果这个点的price比total_price还大，那么就不用访问了 } for(i=1;i<num;i++) { scanf("%d%d",dp[key][j]+dp[s][k]); } } } } int main() { while(cin>>num>>total_price&&((num+1)||(total_price+1))) { init(); if(!total_price) { cout<<"0"<<endl; continue; } dfs(1); cout<<dp[1][total_price]<<endl; } }其实对于这个代码还有可以优化的地方，只是这样写比较简单，并且也可以过，所以就省了，如果谁有优化方法，欢迎留言交流！
