10 有依赖的背包问题（分组背包问题 + 树形dp）

比眉伴天荒 2022-08-28 14:58 138阅读 0赞

**1. 问题描述：**

有 N 个物品和一个容量是 V 的背包。物品之间具有依赖关系，且依赖关系组成一棵树的形状。如果选择一个物品，则必须选择它的父节点。如下图所示：

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeXV6aGFuZ196eQ_size_7_color_FFFFFF_t_70_g_se_x_16][]  
如果选择物品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  
来源：[https://www.acwing.com/problem/content/10/][https_www.acwing.com_problem_content_10]

**2. 思路分析：**

**有依赖的背包问题**属于背包问题中的经典问题，本质上是分组背包问题与树形dp问题的结合，我们可以将树中的每一个节点为根节点的子树看成是一个组，通过对每一个根节点使用dp求解出以当前根节点的子树中对应体积的最大价值，因为是树所以需要使用树形dp更新每一个节点对应的值，基于这个思想我们可以定义一个二维数组或者二维列表，其中dp\[u\]\[j\]表示以当前节点u作为根节点的子树中体积不超过j能够获得的最大价值，借助树形dp问题的思想，我们可以使用dfs遍历整棵树，当我们递归返回到上一层的时候（回溯）那么就需要更新对应根节点中对应体积的值，回溯的时候说明当前根节点对应的某一个子树的结果已经求解完成；当我们回溯的时候接下来就是求解分组背包问题了，这里使用到一个技巧来划分每一个组，组内按照背包的体积进行划分（这样可以避免使用选或者不选子树中某一个节点策略时间复杂度高的问题），这样每求解一个当前根节点的孩子，那么就更新一下以当前节点u为根节点以及加入当前孩子对应体积的最大价值；这里实际上的做法不是一开始的时候就将当前根节点的体积放入到背包中，而是先计算加入当前的子节点的对应体积之后能够获得的最大价值，然后再将当前根节点的体积加入到背包中更新对应的背包体积对应的最大价值（先求解子节点对应体积的最大价值然后再加入根节点这样很方便地求解出当前根节点和某一棵子树能够获得的最大价值），由于这个做法是先考虑加入当前的子树对应的体积之后所以可能dp\[u\]\[k\]其中k小于当前根节点的体积所以是不合法的，这个时候需要清空一下这些位置的值，因为要选子节点必须先选择父节点，当前位置都放不下父节点了所以不满足题目要求。其中创建有向图可以使用之前没有[上司的舞会][Link 1]那道题目中做法，也即使用e，ne，h来连接节点与节点之间的关系，本质上与邻接表是一样的（python语言可以使用\[list() for i in range(n + 1)\]）

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeXV6aGFuZ196eQ_size_11_color_FFFFFF_t_70_g_se_x_16][]

**3. 代码如下：**

**python：**

**使用三个数组来建有向图（比较复杂）：**

from typing import List
    
    
    class Solution:
        idx = 1
        # 声明为全局变量这样在方法中才不用传递很多的参数
        v, w, V = None, None, None
    
        # a是b的父节点, a向b连一条边, 这道题目与没有上司的舞会的题目创建图的方式是一样的都是利用
        # e, ne, h三个数组进行连接
        def add(self, e: List[int], ne: List[int], h: List[int], a: int, b: int):
            e[self.idx] = b
            ne[self.idx] = h[a]
            h[a] = self.idx
            self.idx += 1
    
        def dfs(self, e: List[int], ne: List[int], h: List[int], dp: List[List[int]], u: int):
            i = h[u]
            while i != -1:
                # 注意son=e[i]应该写入到循环中之前写到外面是错误的, 因为在递归的时候需要更新相同父节点的邻边
                son = e[i]
                self.dfs(e, ne, h, dp, son)
                i = ne[i]
                # 下面就是分组背包问题, 其中dp[u][j]表示以当前的节点u为根节点体积不超过j能够获得的最大价值, 下面self.V - self.v[u]是为了给当前的根节点预留一下位置, 先计算子树中对应体积的最大值然后更新根节点的体积更新到dp数组对应的体积中, 最后因为之前使用过dp[u][k], 其中一开始计算的是子树的值没有将根节点的体积计算到背包中所以dp数组中k小于v[u]的dp[u][k]可能存在值的这个时候需要将其清空才是正确的
                for j in range(self.V - self.v[u], -1, -1):
                    for k in range(j + 1):
                        # 这里使用到的一个技巧是对于每一棵子树里面使用体积来划分
                        dp[u][j] = max(dp[u][j], dp[u][j - k] + dp[son][k])
            # 将当前的根节点对应的物品放入到背包(父节点)
            for j in range(self.V, self.v[u] - 1, -1):
                dp[u][j] = dp[u][j - self.v[u]] + self.w[u]
            # 将根节点中小于根节点体积的位置清空, 之前由于先计算子树对应体积所以可能里面的位置是有值的
            for j in range(self.v[u]):
                dp[u][j] = 0
    
        def process(self):
            n, V = map(int, input().split())
            # 先存储0这样下标可以从0开始
            w = [0]
            v = [0]
            self.v = v
            self.w = w
            self.V = V
            root = 0
            e, ne, h = [0] * (n + 1), [0] * (n + 1), [-1] * (n + 1)
            dp = [[0] * (V + 1) for i in range(n + 1)]
            for i in range(1, n + 1):
                _v, _w, p = map(int, input().split())
                v.append(_v)
                w.append(_w)
                # p = -1的时候属于根节点
                if p == -1:
                    root = i
                else:
                    # 使用e, ne, h创建有向图
                    self.add(e, ne, h, p, i)
            self.dfs(e, ne, h, dp, root)
            return dp[root][V]
    
    
    if __name__ == "__main__":
        # 测试数据:
        # 3 5
        # 1 6 -1
        # 4 3 1
        # 5 4 1
        print(Solution().process())

**使用列表来建有向图（比较直观）：**

from typing import List
    
    class Solution:
         def dfs(self, u: int, g: List[List[int]], dp: List[List[int]]):
              for next in g[u]:
                   self.dfs(next, g, dp)
                   for j in range(self.V - self.v[u], -1, -1):
                        for k in range(j + 1):
                             dp[u][j] = max(dp[u][j], dp[u][j - k] + dp[next][k])
              for j in range(self.V, self.v[u] - 1, -1):
                   dp[u][j] = dp[u][j - self.v[u]] + self.w[u]
              for j in range(self.v[u]):
                   dp[u][j] = 0
         
         # 定义三个全局变量这样不用在方法中传递很多的参数
         v, w, V = None, None, None
         def process(self):
              n, V = map(int, input().split())
              self.V = V
              # dp[u][j]表示以u为根节点且体积不超过j的最大价值
              dp = [[0] * (V + 1) for i in range(n + 1)]     
              root = -1
              v, w = [0] * (n + 1), [0] * (n + 1)
              # 使用列表来表示图
              g = [list() for i in range(n + 1)]
              for i in range(1, n + 1):
                   _v, _w, p = map(int, input().split())
                   # p = -1为根节点
                   if p == -1:
                        root = i
                        v[i] = _v
                        w[i] = _w
                   else:
                        v[i] = _v
                        w[i] = _w
                        g[p].append(i)
              self.v = v
              self.w = w
              self.dfs(root, g, dp)
              return dp[root][V]
    
    
    if __name__ == "__main__":
         print(Solution().process())

**c++：**

#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];
    
    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]);
        }
    
        // 将物品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;
    }

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeXV6aGFuZ196eQ_size_7_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/3738a94ec49a4b548595f50397b007b4.png
[https_www.acwing.com_problem_content_10]: https://www.acwing.com/problem/content/10/
[Link 1]: https://blog.csdn.net/qq_39445165/article/details/120291458
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeXV6aGFuZ196eQ_size_11_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/1e1367db57e4442c89f56c2a1fd58b52.png