树形依赖背包的两种实现形式

这里选取 洛谷 P2014 选课作为背景

第一种代码复杂度为O（N*V^2)

第二种代码复杂度为O(N*V)

代码

第一种代码转载至：https://blog.csdn.net/sdz20172133/article/details/82954419

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
using namespace std;
const int N=310;
struct node
{
	int v;///终端点
    int next;///下一条同样起点的边号
    int w;///权值
}edge[N*2];///无向边，2倍
int head[N];///head[u]=i表示以u为起点的所有边中的第一条边是 i号边
int tot;  ///总边数
int minn;
void add(int u,int v)
{
	edge[tot].v=v;
	//edge[tot].w=w;
    edge[tot].next=head[u];
    head[u]=tot++;
}
int n,m;
int dp[N][N],val[N];
void dfs(int u,int fa) 
{
	dp[u][1]=val[u];///选一个肯定选自己这个结点
	for(int i=head[u];i!=-1;i=edge[i].next)
	 {
	 	int v= edge[i].v;
	    ///if(fa==v) continue;   ///如果下一个相邻节点就是父节点，则证明到底层了，开始递归父节点的兄弟节点
		dfs(v,u);
        ///分组背包
		for(int j=m;j>0;j--)    ///背包容量，倒叙，保证没有重复的物品
			for(int k=0;k<j;k++)   ///选择用户
		{
		    dp[u][j]=max(dp[u][j],dp[u][j-k]+dp[v][k]);
		}
	 }
 
}
int main()
{
    while(~scanf("%d%d",&n,&m))
	{
	if(n==0&&m==0) break;
	memset(head,-1,sizeof(head));
    memset(dp,0,sizeof(dp)); 
  	tot=0;
 
  	for(int i=1;i<=n;i++)
	{
		int w,v;
		scanf("%d%d",&v,&w);
		add(v,i);	
		val[i]=w;///题目直接给出第i节课的值	
	}
 
	m++;      ///我们可以0当作根节点，因为有的课可能没有先修课
	val[0]=0;///虚拟构造了结点0
    dfs(0,-1);
	printf("%d\n",dp[0][m]);
	}
	
    return 0;
}
           

第二种优化算法

#include<cstdio>
#include<cstring>
#include<algorithm>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define ll long long
using namespace std;
#define maxn 400

struct Edge{
    int v, next;
}edge[maxn];

int head[maxn], cnt, n, m;
int c[maxn];
int F[maxn][maxn];

void init(){
    memset(head, -1, sizeof(head));
}

void add_edge(int u, int v){
    edge[cnt].v = v;
    edge[cnt].next = head[u];
    head[u] = cnt++;
}

void Dp(int now, int iV)
{
    if (iV <= 0) return ;
    for (int i = head[now]; i != -1; i = edge[i].next)
    {
        int v = edge[i].v;
        for (int k = 0; k < iV; k ++) F[v][k] = F[now][k] + c[v];
        Dp(v, iV - 1);
        for (int k = 1; k <= iV; k ++) F[now][k] = max(F[now][k], F[v][k - 1]);
    }
}

int main(){
    int i, j, k, u, w;
    scanf("%d%d",&n,&m);
    init();
    for(i = 1; i <= n; i++){
        scanf("%d%d",&u,&w);
        add_edge(u, i);
        c[i] = w;
    }
    Dp(0,m);
    printf("%d\n",F[0][m]);
}