樹形依賴背包的兩種實作形式

這裡選取 洛谷 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]);
}