【题目描述】
在大学里每个学生，为了达到一定的学分，必须从很多课程里选择一些课程来学习，在课程里有些课程必须在某些课程之前学习，如高等数学总是在其它课程之前学习。现在有N门功课，每门课有个学分，每门课有一门或没有直接先修课（若课程a是课程b的先修课即只有学完了课程a，才能学习课程b）。一个学生要从这些课程里选择M门课程学习，问他能获得的最大学分是多少？
【输入格式】
第一行有两个整数N,M用空格隔开。(1<=N<=300,1<=M<=300)
接下来的N行,第I+1行包含两个整数ki和si, ki表示第I门课的直接先修课，si表示第I门课的学分。若ki=0表示没有直接先修课（1<=ki<=N, 1<=si<=20）。
【输出格式】
只有一行，选M门课程的最大得分。
【代码】
1. 多叉转二叉
1 /* 2 User:Mandy.H.Y 3 Language:c++ 4 Problem:course 5 */ 6 #include<bits/stdc++.h> 7 using namespace std; 8 const int maxn = 320; 9 int f[maxn][maxn] , bro[maxn] , son[maxn], v[maxn]; 10 void add(int fa, int s) 11 //类似链表的存储 12 { 13 bro[s] = son[fa]; 14 //son[i]中存入i的第一个儿子 15 son[fa] = s; 16 //bro[i]中存入i的上一个兄弟 17 } 18 19 int dp(int i, int j) 20 //对于每一个i节点， 21 //定义dp(i,j)为i的所有兄弟和 i 的所有儿子，和 i 自己，学 j 门课的最大学分总和。 22 { 23 if (i==-1) return 0; 24 if (j==0) return 0; 25 if (f[i][j] != -1) return f[i][j]; 26 //记忆化 ，必备，在下面循环中son与bro有些会重算 27 int m = -1<<30; 28 //最小值 29 30 // 全分兄弟 31 m = max( m, dp(bro[i] , j)); 32 33 for (int k = 0; k <= j-1; k++) 34 //从0开始，表示不选 儿子，选i自己与j-1个兄弟 35 { 36 m = max( m , dp(son[i] , k) + dp(bro[i] , j-1-k) + v[i]); 37 /*那么，可以分成两种情况： 38 1、不学 i 这门课，全部学兄弟的课程，dp( i , j ) = dp( bro[ i ] , j) 39 2、学 i 以及以 i 为先修课的课程， dp( i , j ) = dp( bro[ i ] , j - 1 - k ) + dp( son[ i ] , k ) + v[ i ]*/ 40 } 41 f[i][j] = m; 42 return m; 43 } 44 int main() 45 { 46 memset(son , -1, sizeof(son)); 47 memset(bro , -1, sizeof(bro)); 48 memset(f , -1, sizeof(f )); 49 //初始化，必备，dfs中要用于判断 、，用0易混淆，易错 50 int n, m; 51 cin>>n>>m; 52 for(int i=1;i<=n;i++){ 53 int fa,vx; 54 cin>>fa>>vx; 55 add(fa,i); 56 v[i] = vx; 57 } 58 cout<<dp(0, m+1); 59 return 0; 60 }
2. 背包
1 /* 2 User:Mandy.H.Y 3 Language:c++ 4 Problem:course 5 */ 6 #include<bits/stdc++.h> 7 using namespace std; 8 9 int m,n,head[305],next1[305],f[305][305]; 10 11 void readdata() 12 { 13 scanf("%d%d",&n,&m); 14 for(int i=1;i<=n;i++) 15 { 16 int a; 17 scanf("%d%d",&a,&f[i][0]); 18 //a是第i门的直接先修课 19 //当a等于0时，无父亲的节点便接到0节点上，使树有且只有一个根 20 next1[i]=head[a]; 21 head[a]=i; 22 } 23 } 24 25 void init() 26 { 27 freopen("cour.txt","r",stdin); 28 freopen("cour.txt","w",stdout); 29 } 30 31 int deep(int x) 32 { 33 if(head[x]==0) return 0; 34 int zi=0; 35 //指已算过的科目的总数 36 for(int i=head[x];i!=0;i=next1[i]) 37 { 38 int izi=deep(i); 39 //t表示i的子结点的个数 40 zi=zi+izi+1; 41 for(int j=zi;j>=0;j--) 42 //01背包，一定要是降序,否则可能一个科目选两遍 43 for(int k=0;k<=izi;k++) 44 if(j-k-1>=0&&f[x][j-k-1]+f[i][k]>f[x][j]) f[x][j]=f[x][j-k-1]+f[i][k]; 45 //如果（还有空间选i及i的k个子结点） 46 } 47 return zi; 48 } 49 50 void work() 51 { 52 deep(0); 53 printf("%d",f[0][m]); 54 } 55 56 int main() 57 { 58 //init(); 59 readdata(); 60 work(); 61 return 0; 62 }