深谈树形背包（有依赖的背包）

摆烂小白敲代码

发布于 2024-09-23 16:40:45

3370

文章被收录于专栏：学习学习

树形背包也叫有依赖的背包，是一种背包问题的变体，与传统的背包问题不同的是，物品之间存在一定的层次结构，形成了一棵树。每个节点代表一个物品，节点之间通过边连接，表示层次关系。问题的目标是在遍历这棵树的过程中，选择一些物品放入背包，使得背包中物品的总价值最大。在树形背包问题中，一个节点可以选择放入背包，也可以选择不放入背包。如果选择放入，就需要考虑该节点的子节点；如果选择不放入，可以考虑其他兄弟节点。问题的关键是如何在遍历树的过程中，动态规划地计算每个节点的状态。

这个树形结构选择才出现了有依赖，选这个物品，就要确保它的所有结点都被选择了，才能选择它，有点类似于数据结构中的拓扑序列，只有前面的都做完了才能选择做它，做它是有前提的，比如：学习数据结构是不是先要学习C/C++，C/C++是数据结构的先导课程。

这里用acwing上的例题：10. 有依赖的背包问题 - AcWing题库

话不多少直接上代码，注释在代码上。

#include<iostream>
using namespace std;
int N,V,p,root;//N个物品V背包容量
int v[105],w[105];
int a[105][105],b[105],f[105][105];
//a[i][j]表示以i为头结点有j个子节点，a[i][j]则存的是下标，b[i]表示以i为根结点有b[i]个子节点
//f[i][j]表示以i为根节点，背包容量为j所获得的最大价值
void dfs(int t){//有树就要考虑遍历用dfs深搜，t表示此时父节点
//此时t为父节点，要想选下面的，前提就是把父节点选了，所以初始背包容量大于v[t]都初始化w[t]
    for(int i=v[t];i<=V;i++){
        f[t][i]=w[t];
    }
//下面不是一个父节点有许多子节点，按个遍历初始化它们，那么身为子节点又是父节点，又有子节点，递归下去
    for(int i=0;i<b[t];i++){
        int s=a[t][i];
        dfs(s);
        for(int j=V;j>=v[t];j--){//类似01背包逆序遍历
            for(int k=0;k<=j-v[t];k++){
                f[t][j]=max(f[t][j],f[t][j-k]+f[s][k]);//状态转移方程
                //f[t][j-k]+f[s][k]表示父节点要j-k的容量，子节点要k的容量
            }
        }
    }
}
int main(){
    cin>>N>>V;
    for(int i=1;i<=N;i++){
        cin>>v[i]>>w[i]>>p;
        if(p==-1){//-1表示为根节点
            root=i;
        }else{
            a[p][b[p]++]=i;//可以看一下上面a[i][j]与b[i]的含义
        }
    }
    dfs(root);
    cout<<f[root][V]<<endl;
    return 0;
}