acwing-10 有依赖的背包问题

来源:

AcWing 10. 有依赖的背包问题

参考:

题目描述

$N$ 个物品和容量为 $V$ 的背包，物品间有树形依赖关系：选子节点必须先选父节点。求最大价值。

数据范围

$1 \leq N, V \leq 100$
$1 \leq v_{i}, w_{i} \leq 100$

示例

输入：
5 7
2 3 -1    # 物品1: 体积2, 价值3, 根节点
2 2 1     # 物品2: 体积2, 价值2, 父节点为1
3 5 1     # 物品3: 体积3, 价值5, 父节点为1
4 7 2     # 物品4: 体积4, 价值7, 父节点为2
3 6 2     # 物品5: 体积3, 价值6, 父节点为2

输出：11

思路

树形 DP + 分组背包。自底向上处理，每个子树视为泛化物品，用分组背包方式合并。

状态定义

$d p [u] [j]$ = 以 $u$ 为根的子树中，体积不超过 $j$ 且必选 $u$ 的最大价值

转移方程

对节点 $u$ 的每个子节点 $s$ ，枚举分配给子树 $s$ 的体积 $k$ ：

d p [u] [j] = 0 \leq k \leq j - v_{u} max (d p [u] [j - k] + d p [s] [k])

复杂度

时间： $O (N \cdot V^{2})$
空间： $O (N \cdot V)$

代码

两种写法，复杂度相同，思路略有不同。

写法1: 分组背包（教科书式）

先递归处理子树，再倒序枚举合并。易理解，适合初学。

void dfs_grouped(int u, int V, const vector<Item>& items, vector<vector<int>>& dp) {
    // 初始化：必选 u
    for (int j = items[u].v; j <= V; ++j)
        dp[u][j] = items[u].w;
 
    for (int s : items[u].sons) {
        dfs_grouped(s, V, items, dp);  // 先递归
 
        // 分组背包合并，倒序枚举避免重复使用子树
        for (int j = V; j >= items[u].v; --j) {
            for (int k = 0; k <= j - items[u].v; ++k) {
                dp[u][j] = max(dp[u][j], dp[u][j - k] + dp[s][k]);
            }
        }
    }
}

要点：

倒序枚举 $j$ ：0-1 背包特性，确保每个子树只用一次
$k$ 的上界是 $j - v_{u}$ ：必须给当前节点留出空间

写法2: 泛化物品求并

利用”选子树 $s$ “与”不选子树 $s$ “互斥，正序遍历后直接取 max 合并。

void dfs_union(int u, int V, int cur_v, const vector<Item>& items, vector<vector<int>>& dp) {
    // cur_v: 根到 u 路径的体积和（已占用的下界）
    if (cur_v > V) return;
 
    for (int s : items[u].sons) {
        int new_v = cur_v + items[s].v;
 
        // 初始化 dp[s]：在 dp[u] 基础上加入 s
        for (int j = new_v; j <= V; ++j)
            dp[s][j] = dp[u][j - items[s].v] + items[s].w;
 
        dfs_union(s, V, new_v, items, dp);  // 递归
 
        // 合并：不选 s 子树 vs 选 s 子树，二者互斥
        for (int j = new_v; j <= V; ++j)
            dp[u][j] = max(dp[u][j], dp[s][j]);
    }
}

要点：

无需倒序：dp[u] 和 dp[s] 表示互斥的两种选择，直接取 max
cur_v 参数：追踪路径体积和，用于剪枝和确定枚举下界
更简洁，但需理解互斥性

对比

写法	枚举顺序	核心思想	适用场景
分组背包	倒序	0-1背包防重复	易理解，通用
泛化物品求并	正序	互斥选择取max	代码简洁

易错点

忘记初始化 dp[root]
写法1 中 $j$ 必须倒序
$k$ 的上界是 $j - v_{u}$ 而非 $j$
写法2 中需正确传递 cur_v

Sean's Blog

探索