有依赖的背包问题

例题

背包和树形dp的结合版

这个题目是一个树的形式，所以用递归的思路来考虑

因为如果要选择子节点，必须要选择根节点，所以用递归比较方便

集合划分的时候，先将集合按照子树有多少划分一下，然后再按照体积划分一下

这里不同于金明的预算方案，金明的预算方案是按照方案来进行划分，因为它的方案数比较少，而这个题目中方案数比较多，因为节点个数可能很多，所以用体积来划分，就比如，左边第一个子树，用的体积是0的情况下，它的最大价值是多少，体积是1。。。依次往后推，一共m+1种选法（体积最大是m）

这样就能看成是一个分组背包，把每一个子树看成是一个物品组。每个物品组有m+1个物品，第0个物品表示体积是0，价值是f[0]，第五个表示是，体积是5，价值是f[5]，第m类表示体积是m，价值是f[m]，其实就是把每一个子树看成是一个物品组，每一个物品组种只能选一个

dp是怎么优化的呢？就是用某个数表示一类

本质上是一个树形dp的框架，然后在树形dp的框架之下，我们每一次就只需要考虑，当前的根节点和它的子节点之间的关系，就只需要考虑两层之间的关系，在考虑两层之间关系的时候，我们可以发现，可以把每一个子树，看成是一个物品组，这就是一个分组背包的问题，就可以用分组背包的方式解决

#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 110;

int n, m;
int v[N], w[N];
int h[N], e[N], ne[N], idx;
int f[N][N];//存的i是点的编号，j是用了多少体积

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

void dfs(int u)
{
    
    for (int i = h[u]; ~i; i = ne[i])   // 循环物品组
    {
    
        int son = e[i];
        dfs(e[i]);

        // 分组背包
        for (int j = m - v[u]; j >= 0; j -- )  // 循环体积
            for (int k = 0; k <= j; k ++ )  // 循环决策
                f[u][j] = max(f[u][j], f[u][j - k] + f[son][k]);
    }
    //自我感觉可以这么考虑，就是分配给这个子树了j体积，如果j大于v[u]，说明在子树中选了东西，所以u一定要加进去
    // 将物品u加进去
    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;
}

int main()
{
    
    cin >> n >> m;

    memset(h, -1, sizeof h);
    int root;
    for (int i = 1; i <= n; i ++ )
    {
    
        int p;
        cin >> v[i] >> w[i] >> p;
        if (p == -1) root = i;
        else add(p, i);
    }

    dfs(root);

    cout << f[root][m] << endl;

    return 0;
}