思路

将物品依赖关系树的支链看做不同背包组, 进行dfs

c++ 树形dp：有依赖的背包

#include <bits/stdc++.h>
using namespace std;

const int N=105;
int n,m;
int v[N], w[N];
int f[N][N];
vector<int> G[N];

// 分组背包问题
void dfs(int node){
    for(auto &_node: G[node]){ // 物品组
        dfs(_node);
        for(int j=m-v[node]; j>=0; --j) // 循环体积, 预留父节点体积空间
            for(int k=0; k<=j; ++k) // 循环决策
                f[node][j]=max(f[node][j], f[node][j-k]+f[_node][k]);
    }
    // 考虑父节点, 加入物品node
    for(int i=m; i>=v[node]; --i) f[node][i]=f[node][i-v[node]]+w[node];
    for(int i=0; i<v[node]; ++i) f[node][i]=0;
}

int main(){
    cin>>n>>m;
    int root; // 记录根节点
    int p;
    for(int i=1; i<=n; ++i){
        cin>>v[i]>>w[i]>>p;
        if(p==-1) root=i;
        else G[p].push_back(i);
    }

    dfs(root);
    cout<<f[root][m]<<endl;

    return 0;
}

python

from typing import List
class Solution:
    def main(self, n:int, m:int, root:int, v:List[int], w:List[int], G:List[List[int]]):
        f = [[0 for _ in range(m+1)] for _ in range(n+1)]
        def dfs(node):
            for _node in G[node]:
                dfs(_node)
                for j in range(m-v[node]+1)[::-1]:
                    for k in range(j+1):
                        f[node][j]=max(f[node][j], f[node][j-k]+f[_node][k])
            for i in range(v[node], m+1)[::-1]: f[node][i]=f[node][i-v[node]]+w[node]
            for i in range(v[node]): f[node][i]=0

        dfs(root)
        print(f[root][m])

if __name__ == '__main__':
    n, m=map(int, input().split())
    root=-1
    v, w=[0], [0]
    G=[[] for _ in range(1+n)]
    for i in range(1, n+1):
        _v, _w, p=map(int, input().split())
        v.append(_v)
        w.append(_w)
        if p==-1: root=i
        else: G[p].append(i)

    sol=Solution()
    sol.main(n, m, root, v, w, G)