http://acm.hdu.edu.cn/showproblem.php?pid=1561
树形dp+有依赖的背包。==分组背包。
思路：
思路：参考《背包九讲》
分组背包：将物品分成k组，每组中有若干件物品，并且这些物品两两互斥（既对于第 i 组物品，只能选该组物品的其中一个，或者一个也不选），求在一定的背包容量下如何选得最大值。
依赖背包：对于要选物品b，必须在选择a的情况下才能选，这样的背包问题称为有依赖的背包。普通的有依赖的背包很容易转换成分组背包来做，假如要选c必须先选a，要选b也必须先选a，若a,b,c的价值分别为Va,Vb,Vc,容量分别为Ca,Cb,Cc,则可以将这三件物品构成一个分组，假设最大容量为V，对b,c在容量为（V-Ca）（因为a必选）的条件下进行01背包，得到在这样的容量下的最优解。其中最优解分别存在dp[0...V-Ca]+Va，把这些最优解当成新物品来用（这些新物品构成一个分组，因为这里已经包含了对b,c的所有选择情况了，不同的选择肯定是互斥的）。把所有依赖关系进行分组后，直接分组背包的做法。（所谓普通的分组背包，其实也就是若b依赖a，则b不能再被其他物品依赖，既不存在先选a才能选b，先选b才能选c这样的链式关系。）
然而，往往存在一般情况，也就是题目给出的就是链式关系。若把不依赖于任何物品的物品当作根节点，那么这样的链式关系可以构成一棵树，没被其他物品依赖的物品就是叶子。这就是基础的树形DP，若某节点的所有孩子都是叶子，那么这个节点跟它的孩子可以构成一个分组。
注意：len=1开始，容量为m+1。
Time Limit: 6000/2000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 4889 Accepted Submission(s): 2885
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52 |
#include<iostream>#include<cstring>#include<cstdio>using
namespace std;int dp[205][205],n,m,len;//dp[x][y]表示以x为根节点，选择了j件物品int head[205];struct
node{ int
now,next,val;}tree[205];void
add(int
x,int y,int v){ tree[len].now=y; tree[len].val=v; tree[len].next=head[x]; head[x]=len++;}void
dfs(int
root){ int
i,j,k,son; for(i=head[root];i!=-1;i=tree[i].next) { //说明有孩子，往下搜，直到搜到叶子为止 son=tree[i].now; dfs(son); for(j=m+1;j>=1;j--)//背包容量为M+1，是因为多条链式关系，不能构成树，加入一个根节点0，其价值为0，所以有M+1的容量。 for(k=1;k<j; k++)//k<j，就是相当于V-Ca<V，a是必选的，容量为1 dp[root][j] = max(dp[root][j],dp[root][j-k]+dp[son][k]+tree[i].val); //dp[to][k]是已经搜过的,是新物品 }}int
main(){ int
i,a,b; while(~scanf("%d%d",&n,&m)&n!=0&m!=0) { len=1;//len=0,是根节点，一定要注意。 memset(dp,0,sizeof(dp)); memset(head,-1,sizeof(head)); for(i=1;i<=n;i++) { scanf("%d%d",&a,&b); add(a,i,b); } tree[0].val=0; dfs(0); printf("%d\n",dp[0][m+1]); } return
0;} |
HDU 1561 The more, The Better,布布扣,bubuko.com
原文：http://www.cnblogs.com/cancangood/p/3667314.html