个人技术分享

算法提高之有依赖的背包问题

• 核心思想：分组背包 + 树形dp

  • 因为不取父节点，子节点取不了 所以dfs递归从子节点开始，向上返回
  • f[i][j]表示以i为根节点总体积不超过j的方案

•   #include <iostream>
    #include <cstring>
    #include <algorithm>
    
    using namespace std;
    const int N = 110;
    
    int e[N],ne[N],h[N],idx;
    int v[N],w[N];
    int f[N][N];
    int n,m,root;
    
    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(son);
            for(int j=m-v[u];j>=0;j--)  //确保能取到当前父节点 预留v[u]的体积
            {  
                for(int k=0;k<=j;k++)  //子节点占用的体积
                {
                    //01背包 j从大到小 求f[u][j]时f[u][j-k]还没更新 即当前子节点没有算进去
                    f[u][j] = max(f[u][j] , f[u][j-k] + f[son][k]);
                }
            }
        }
        //所有能放当前父节点的都放一下
        for(int j=m;j>=v[u];j--) f[u][j] = f[u][j-v[u]] + w[u]; 
        //所有放不了父节点的全部清空 放不了父节点-->什么都放不了
        for(int j=0;j<v[u];j++) f[u][j] = 0;
    }
    int main()
    {
        cin>>n>>m;
        memset(h, -1, sizeof h);
        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;
    }