$$\color{Red}{有依赖的背包：j为什么倒序？更好理解的dfs版本!}$$

这里附带打个广告——————我做的所有的题解

包括基础提高以及一些零散刷的各种各样的题

题目介绍

有 N 个物品和一个容量是 V 的背包。

物品之间具有依赖关系，且依赖关系组成一棵树的形状。如果选择一个物品，则必须选择它的父节点。

如果选择物品5，则必须选择物品1和2。这是因为2是5的父节点，1是2的父节点。

每件物品的编号是 i，体积是 vi，价值是 wi，依赖的父节点编号是 pi。物品的下标范围是 1…N。

求解将哪些物品装入背包，可使物品总体积不超过背包容量，且总价值最大。

输出最大价值。

输入格式

第一行有两个整数 N，V，用空格隔开，分别表示物品个数和背包容量。

接下来有 N 行数据，每行数据表示一个物品。
第 i 行有三个整数 vi,wi,pi，用空格隔开，分别表示物品的体积、价值和依赖的物品编号。
如果 pi=−1，表示根节点。 数据保证所有物品构成一棵树。

输出格式
输出一个整数，表示最大价值。

数据范围

1 ≤ N, V ≤ 100

1 ≤ vi, wi ≤ 100

父节点编号范围：

内部结点：1≤pi≤N

根节点 pi=−1

输入样例：

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

输出样例：

11

思考

本题最好和下面这两道题对比来看，分别是有依赖的分组背包，有依赖的背包以边划分的二叉苹果树，学会这两道题，对理解这道题很有帮助

我的金明的预算方案详细题解

我的二叉苹果树详细题解

这道题不愧是困难题，相信我的题解能把很多你没考虑的坑，或者是细节问题都暴露出来，可能你和之前的我一样没有真正理解这道题

我们先看y总思路这里的思考：设立两维f[i][j]代表选取i为根节点，包含该节点的子树最大体积划分为j的集合中，最大的值存储

那么我们分析这种依赖关系的DP应该是树形DP，可以通过dfs从子树不断更新到整棵树。
每当选择好一个根节点，判断它这个集合其实可以看作遍历它的所有子节点，一个子节点可以看作一组，选或不选这个子节点为根的子树，不同的子树形状或者说范围，代表一组物品中的一个物品。

因为我们这里有一个先决条件，我们枚举一棵树为根节点，首先得满足必须把这个节点选取到

所以可以看作分组背包前，先得满足一个体积条件v[x]下才能进一步去进行分组背包，若连根节点都没法选，即j < v[x]，也就没有意义再进行子节点的分组背包枚举，这种情况下的f[x][j]连根节点都无法选择，自然价值应该是0

y总这里为了满足能够做到把上述的先决条件达到，类似于01背包，预留给v[x]一个体积，和它的价值，先进行体积最大为m - v[x]的分组背包，然后再按情况进行循环i判断，能否放下根节点，能放下就给放得下v[x]的状态方程赋值:f[x][i] = f[x][i - v[x]] + w[x],若放不下，直接给它赋值f[x][i] = 0

下面第一组代码就是y总思路的代码，看完上面的就大概理解整体思路。

但是有两个地方很容易让人奇怪：1. 为什么分组背包部分要从j = m - v[x]倒序枚举？

我们此前一旦用到倒序，都是在压缩维度的情况下，更新i维度的方程f[i][j]需要用到i - 1的维度方程f[i-1][j - *]更新，一旦压缩i维度，如果还是正序，就会出现因为没有i维度作为标识，更新大的j方程会用到小的j方程的时候，当前更小的j方程已经被更新成i的维度了，不是我们想要的i-1维度。故需要倒序j进行赋值。

但这道题我们没有压缩维度啊？为什么这里还倒序j了？你们可以试试不倒序这道题就AC不了了

这里我通过翻阅各种题解，终于找到来自小虎成员大佬合理的解释——>
其实这里y总是简化了代码，本来是三维的状态，f[x][i][j],表示以x为根的子树，的前i个子节点子树中选，总体积最大为j的所有集合，
每次去循环以x节点为跟的子树，并循环体积，一个子树相当于一个组，一组内不同方案，相当于选择不同体积，
只看后面两个[i] [j]代表的是在前i个组中选，总体积不超过j的所有集合，属性max,然后还要枚举每一组内，分配多少体积，才能求出最大值
所以f[x] [i] [j] = max ( f[x] [i] [j],f[x] [i-1] [j-k] + f[y] [yi] [k])
然后进行优化，由于每次都用到上一维的状态，和子树y最后yi的状态，所以可以把第二维优化变成
f[x] [j] = max(f[x] [j] , f[x] [j-k] + f[y] [k]) 这里注意枚举体积的时候需要倒着枚举

void dfs(int x){
    //进行初始化，当体积小于v[x]的时候是0，大于等于v[x]的时候是w[x]
    for(int j=v[x];j<=m;j++) f[x][0][j]=w[x];
    for(int i=1;i<son[x].size();i++){
        int u=son[x][i];
        int u_son=son[u].size()-1;
        dfs(u);
        for(int j=v[x];j<=m;j++){  //这里从v[x]开始，因为至少要包含x根节点
            for(int k=0;k<=j-v[x];k++){
                f[x][i][j]=max(f[x][i][j],f[x][i-1][j-k]+f[u][u_son][k]);
            }
        }
    }
}

此时再回头看，我们就说的通了，为什么y总加上根节点这么一个操作，需要在完全把所有子树的分组背包做完才做了。因为我们求的是x为根，在分组i即子节点中选择形态各异的子树（可以为0），这些一个个子树由根节点的不同分成不同组，同一组内，由形态的不同分为不同的物品，最终完成分组背包的建模。同时选择体积为j，这里y总把这个i维度优化掉了，本身我们遍历到一个新的子节点（新的组）的情况下，原先的分组可选可不选的情况值应该还得存在于对应的方程内部，这里压缩i这一维还正序遍历体积，显然还会出现刚刚我说的污染问题。这也是为什么要倒序遍历体积，看上去是这道题按体积划分的，其实还是可以看作按状态划分，只是用一个体积的值，把形态各异的状态的集合直接整体表示了。

2.为什么y总的代码要dfs遍历完子节点结束后，再去给相应的选取根节点的真正的方程，倒序的情况加上w[x]

        // 现在把应该添加的选取的根节点x的价值加上
        for (int i = m; i >= v[x]; i--)
            f[x][i] = f[x][i - v[x]] + w[x];
        for (int i = 0; i < v[x]; i++)
            f[x][i] = 0;

有了上面的了解我们就知道，这里我们压缩了选前i组的这个i维度，我们倒序体积进行更新是因为，f[x][i]需要用更小体积的f[x][i - v[x]]方程更新数值，正序没有i这个维度区分，还选择正序遍历，就会把更小的f[x][i - v[x]]提前赋值，就污染了我们的方程更新的起点。

这样看这道题代码太复杂了，我怎么能做到不去做最后这步的把根节点加上的操作，让逻辑更通畅？

之前y总那么做的原因就是因为没有做到一开始状态转移赋初值，即能转移过来的情况，加上w[x]，不能转移过来的情况我们直接赋值为0，然后枚举体积j直接不让小于v[x]的情况能转移过来。而子树最多也就分配j - v[x]体积，此时就不需要最后进行根节点判断是否能放下，同时还要把不能的情况给初始化为0，然后能转移的还要倒序更新。

    static void dfs(int x) {
        for (int i = v[x]; i <= m; i++)
            f[x][i] = w[x];

        for (int i = h[x]; i != -1; i = ne[i]) {
            int son = e[i];
            dfs(son);
            // 枚举体积 这里大于v[x]代表我们小于的情况下就无法转移到后续的状态，默认是0
            for (int j = m; j >= v[x]; j--) {
                // 枚举决策 这里k最大为 j - v[x]是因为更大就无法容纳根节点x了，最多只能给子树分配 j - v[x]
                for (int k = 0; k <= j - v[x]; k++) {
                    f[x][j] = Math.max(f[x][j], f[x][j - k] + f[son][k]);
                }
            }
        }
    }

java 初始化初值升级版

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;

public class Main {
    static int N = 110, n, m, idx;
    static int[] e = new int[N];
    static int[] ne = new int[N];
    static int[] h = new int[N];
    static int[] w = new int[N];
    static int[] v = new int[N];

    static void add(int a, int b) {
        e[idx] = b;
        ne[idx] = h[a];
        h[a] = idx++;
    }

    static void dfs(int x) {
        for (int i = v[x]; i <= m; i++)
            f[x][i] = w[x];

        for (int i = h[x]; i != -1; i = ne[i]) {
            int son = e[i];
            dfs(son);
            // 枚举体积 这里大于v[x]代表我们小于的情况下就无法转移到后续的状态，默认是0
            for (int j = m; j >= v[x]; j--) {
                // 枚举决策 这里k最大为 j - v[x]是因为更大就无法容纳根节点x了，最多只能给子树分配 j - v[x]
                for (int k = 0; k <= j - v[x]; k++) {
                    f[x][j] = Math.max(f[x][j], f[x][j - k] + f[son][k]);
                }
            }
        }
    }

    static int[][] f = new int[N][N];
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws IOException {
        Arrays.fill(h, -1);
        String[] s1 = br.readLine().split(" ");
        n = Integer.parseInt(s1[0]);
        m = Integer.parseInt(s1[1]);
        int root = 0;
        for (int i = 1; i <= n; i++) {
            String[] s2 = br.readLine().split(" ");
            v[i] = Integer.parseInt(s2[0]);
            w[i] = Integer.parseInt(s2[1]);
            int p = Integer.parseInt(s2[2]);
            if (p != -1)
                add(p, i);
            else root = i;
        }
        dfs(root);
        System.out.println(f[root][m]);
    }
}

java y总思路版

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {
    static int N = 110, idx, n, m, p, root;
    static int[] h = new int[N];
    static int[] e = new int[N];
    static int[] ne = new int[N];
    static int[] w = new int[N];
    static int[] v = new int[N];
    static int[][] f = new int[N][N];
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    static void add(int x, int y){
        e[idx] = y;
        ne[idx] = h[x];
        h[x] = idx++;
    }

    static void dfs(int u){
        // 枚举组：枚举每个子节点 在最大能获得 j - v[u]体积的最大价值
        for (int i = h[u]; i !=-1; i=ne[i]) {
            int son = e[i];
            dfs(son);
            // 枚举决策
            for (int j = m - v[u];j >= 0; j--) {
                for (int k = 0; k <= j; k++) {
                    f[u][j] = Math.max(f[u][j], f[u][j - k] + f[son][k]);
                }
            }
        }
        // 现在把应该添加的选取的根节点x的价值加上
        for (int i = m; i >= v[u]; i--) 
            f[u][i] = f[u][i - v[u]] + w[u];
        for (int i = 0; i < v[u]; i++) 
            f[u][i] = 0;
    }

    public static void main(String[] args) throws IOException {
        Arrays.fill(h, -1);
        String[] s1 = br.readLine().split(" ");
        n = Integer.parseInt(s1[0]);
        m = Integer.parseInt(s1[1]);
        for (int i = 1; i <= n; i++) {
            String[] s2 = br.readLine().split(" ");
            v[i] = Integer.parseInt(s2[0]);
            w[i] = Integer.parseInt(s2[1]);
            p = Integer.parseInt(s2[2]);
            if(p == -1) root = i;
            else add(p, i);
        }
        dfs(root);
        System.out.println(f[root][m]);
    }
}