# 有依赖的背包问题

###### tags: `競程題解`,`競程`

timestamp：2023/1/21 00:55

[題目連結](https://www.acwing.com/problem/content/10/)

簡單來說，就是跟一般的背包問題一樣。
多了個條件就是要拿這個東西必須也要拿取父節點。

解題想法：

> 遞迴dp?(窩不知道有沒有這個詞

照慣例，開個dp陣列

dp[i][j] 節點 i 在擁有 j 個容量下的最大值。

先拿範例來說說吧

5 7
2 3 -1
2 2 1
3 5 1
4 7 2
3 6 2

可以發現，node4 & node5 為葉節點。

那麼
$dp[4][4\sim7]=7$
$dp[5][3\sim7]=6$
如何解釋，只要給節點四分到4~7的容量的話，那麼一定會把節點四放進去，所以都等於7。

接下來，回到節點四以及節點五的父節點去做分配。

至於如何分配呢 就使用兩個for迴圈
去分配說當我現在有 j 個容量在這個點的時候，我分出 k個容量給某個子節點。(11行~15行)

那至於為什麼第 13 行的轉移式為：

dp[now][j]=max(dp[now][j],dp[i][k]+dp[now][j-k]);

而不是

dp[now][j]=max(dp[now][j],dp[i][k]+wi[now]);

可以這樣想，這個dp目前是裝了包含這個節點(now)以及有可能走到的葉節點下，如果說今天這棵樹的每個節點底下都只有一個子節點 那當然可以這樣寫XD(是說這樣就變成一條鍊狀了 根本不用dp)
換句話說，目前這個dp裡面的東西已經存了下一層之後的選擇，所以需要考慮它是十分合理的!

#include "iostream"
#include "vector"
using namespace std;
int dp[110][110]={};
vector<int> g[110];
int vi[110],wi[110],v,n;
void dfs(int now){
    for(int i=v;i>=vi[now];i--)dp[now][i]=wi[now];
    for(int i:g[now]){
        dfs(i);
        for(int j=v;j>=vi[now];j--){
            for(int k=0;k<=j-vi[now];k++){
                dp[now][j]=max(dp[now][j],dp[i][k]+dp[now][j-k]);
            }
        }
    }
    return ;
}
int main(){
    int root;
    cin>>n>>v;
    int p;
    for(int i=1;i<=n;i++){
        cin>>vi[i]>>wi[i]>>p;
        if(p!=-1){
            g[p].push_back(i);
        }
        else root=i;
    }
    dfs(root);
    cout<<dp[root][v];

}