题目描述

blablabla

分组背包

仅作记录，看注释。

时间复杂度

参考文献

C++ 代码

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;

const int N=110;

int f[N][N];            //虽然开了二维，不过第一维是根节点数，对于分组背包部分来说还是一维，需要逆序。
int h[N],e[N],ne[N],idx;        //利用邻接表来存储树
int v[N],w[N];
int n,m;


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!=-1;i=ne[i])   //遍历每一个子节点
    {
        int son=e[i];
        dfs(e[i]);      //递归得到子节点的f值

        for(int j=m-v[u];j>=0;j--)      //体积上界是m-v[u]，要满足能把根节点装进去
        {
            for(int k=0;k<=j;k++)       //根据体积分割几何，所以决策是从0到j
            {   
                f[u][j]=max(f[u][j],f[u][j-k]+f[son][k]);       //注意了！最妙的是f[son][k]代表了k决策的价值！
            }
        }

    }

    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;
}