有依赖的背包问题

#include<bits/stdc++.h>

using namespace std;

const int MAXX = 1e3 + 5;

int n, v, a[MAXX], b[MAXX], dp[MAXX][MAXX], s, fa;
vector<int> e[MAXX];

void dfs(int x){
    for(int i = a[x]; i <= v; i++){
        dp[x][i] = b[x];
    }
    for(int i = 0; i < e[x].size(); i++){
        int ss = e[x][i];
        dfs(ss);
        for(int j = v; j >= 0; j--){
            for(int k = 0; k + a[x] <= j; k++){
                dp[x][j] = max(dp[x][j], dp[x][j - k] + dp[ss][k]);
            }
        }
    }
}

int main(){
    cin >> n >> v;
    for(int i = 1; i <= n; i++){
        cin >> a[i] >> b[i] >> s;
        if(s != -1){
            e[s].push_back(i);
        }else{
            fa = i;
        }
    }
    dfs(fa);
    cout << dp[fa][v];

  return 0;
}