背包九讲——树形背包问题（有依赖的背包）

背包问题第七讲——树形背包问题（有依赖的背包）

背包问题是一类经典的组合优化问题，通常涉及在限定容量的背包中选择物品，以最大化某种价值或利益。问题的一般描述是：有一个背包，其容量为C；有一组物品，每个物品有重量w和价值v。目标是选择一些物品放入背包，使得它们的总重量不超过背包容量，同时总价值最大。
树形背包也叫有依赖的背包，每个节点代表一个物品，节点之间通过边连接，表示层次关系。问题的目标是在遍历这棵树的过程中，选择一些物品放入背包，使得背包中物品的总价值最大。

树形背包问题

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

问题引入：

树形背包之所以叫树形背包，是因为它有一个树形结构，在树形结构选择时才出现了依赖，选这个物品，就要确保它的所有父结点都被选择了，才能选择它，否则它的父节点有一个没有被选择的，那么它就不能被选择。这个特点有点类似于数据结构中的拓扑序列，只有前面的都做完了才能选择做它，做它是有前提的，比如：学习数据结构是不是先要学习C/C++，学习数据结构的前提还有高数，那么高数、C/C++就是数据结构的先导课程，只有学完高数、C/C++才能学习数据结构，这一点与树形背包类似。

下面是拓扑序列的定义：

拓扑序列是顶点活动网中将活动按发生的先后次序进行的一种排列。拓扑排序，是对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序，是将G中所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若边(u,v)∈E(G)，则u在线性序列中出现在v之前。通常，这样的线性序列称为满足拓扑次序(Topological Order)的序列，简称拓扑序列。简单的说，由某个集合上的一个偏序得到该集合上的一个全序，这个操作称之为拓扑排序。

问题解读：

树形背包问题是一种组合优化问题，它是经典的背包问题的扩展。在背包问题中，通常有一组物品和一个背包，每个物品都有一个重量和一个价值，目标是在不超过背包容量限制的情况下，选择一组物品，使得总价值最大化。

树形背包问题则是在背包问题的基础上，引入了树形结构，通常用于描述一些具有层次关系的物品选择问题。在树形背包问题中，物品被组织成一棵树，每个节点代表一个物品，节点之间的边代表物品之间的选择关系。通常，这种关系意味着如果选择了父节点的物品，那么就不能选择其子节点的物品，反之亦然。

树形背包问题的一个典型例子是“旅行商问题”（TSP）的一个变种，其中旅行商需要访问一系列城市，并且每个城市只能访问一次，但可以选择是否访问某个城市。如果选择了某个城市，那么就不能访问它的子城市，这样就形成了一个树形结构。

解决树形背包问题通常需要使用动态规划（Dynamic Programming, DP）算法。动态规划是一种通过将复杂问题分解为更简单的子问题来解决问题的方法，通过存储这些子问题的解（通常是在表格中），可以避免重复计算，从而提高效率。

在树形背包问题中，动态规划的状态可以定义为当前节点以及是否选择了当前节点的物品。状态转移方程需要考虑从当前节点的父节点和子节点转移过来的情况，以及当前节点是否选择了物品。下面一道例题进行实战讲解算法。

算法例题：10. 有依赖的背包问题 - AcWing题库

题目：

有 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

算法实现：

首先我们需要考虑的如何存取这棵树，我们需要一个二维数组a[i][j],表示以i为头结点有j个子节点，a[i][j]则存的是下标，还需要一个一维数组b[i]，表示以i为根结点有b[i]个子节点。我们通过这两个数组a,b把树形给保存下来，方便后面的搜索。再就是二维数组f[i][j]，用于动态规划。

算法开始，我们需要找到头结点，从头结点开始搜索，要想选择下面的，先要选择头结点，那么此时更新f数组，只要背包容量大于头结点的重量，都赋值头结点的价值。再次，我们顺着头结点去找它的子节点，递归的操作，把所有结点递归完成，f数组都更新了一遍。递归到每一个父节点时，此时我就可以拿着f数组去更新了，我们还是根据01背包的一维优化解法为基础，去逆序遍历背包容量，去选择此时父节点下面的子节点，记递归到的父节点为s，前面大父节点为t。以t为基础，去预留出k的空间给以s为父节点的树。

代码实现：

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

视频讲解：E18 树形DP 树上背包 P2014 [CTSC1997] 选课_哔哩哔哩_bilibili

上一篇文章：背包九讲——分组背包问题-CSDN博客

本人水平有限一些地方写的不是很好，都是按照自己的思路写的，或许跟大家有所不同，鼓励大家提出疑问，探讨更好的思路解法，执笔至此，感触彼多，全文将至，落笔为终，感谢大家支持。下篇更新背包求方案数问题。

标签：问题,背包,九讲,选择,树形,物品,节点
From： https://blog.csdn.net/m0_73633807/article/details/142746336