题目描述

有依赖的背包问题

i是子树的根节点编号
d[j][j]是以i为根节点的子树体积为j时的最大价值
那么：
第1组：d[1][0], d[1][1], ..., d[1][j], ..., d[1][v]
第2组：d[2][0], d[2][1], ..., d[2][j], ..., d[2][v]
...
第i组：d[i][0], d[i][1], ..., d[i][j], ..., d[i][v]
...
第n组：d[n][0], d[n][1], ..., d[n][j], ..., d[n][v]

第i组中选择不同的体积代表了针对子树i做出的不同的决策
决策之间互斥，每组中只能选择使得价值最大的，就变成了分组背包问题

对照分组背包：
for 组i in range(所有组)：
    for 体积j in range(总体积, 0, -1):
        for 组内物品k in 组内所有物品:
            if j >= vk:  # vk和wk是物品k的体积和价值
                dp[j] = max(dp[j], dp[j-vk]+wk)
得到本问题：
for i in range(所有节点):  # 循环组 每个节点对应一个组 本题中是某个节点的所有儿子节点
    for j in range(V-v[i], 0, -1):  # 循环体积
        for k in range(0, j+1):  # 循环决策 每个体积对应一个决策 从组内所有决策中选择使得价值最大的
            if j >= k:
                d[i][j] = max(d[i][j], d[i][j-k]+d[son][k])  # 第k个决策的体积vk是k 价值wk是其已经选了的子节点的价值
需要注意：
1. 循环体积的时候从V-v[i]开始：
每次选择一个子节点的时候，我们需要先判断一下背包的体积能不能容纳其父节点
如果可以容纳则选择这个子节点和其父节点 如果不能容纳则不能选择这个子节点 重复这个过程一直到根节点
所以上述循环默认了节点i已经被选择了 因此我们先计算背包体积从 0 到 总体积-节点i的体积 的决策情况（此时节点i是子树的根节点）
然后把当前节点价值加到背包容量足够的决策上
2. 把当前节点价值加到背包容量足够的决策上（也就是体积为v[i]-V的决策上）：
for j in range(V, v[i]-1, -1):  # 背包容量足够就加上当前节点
    f[i][j] = f[i][j - v[i]] + w[j]
for j in range(0, v[j]):  # 背包容量不够就不加当前节点 抛弃当前决策
    f[i][j] = 0

样例

# 输入 ###############################################################################
N, V = map(int, input().strip().split())
data = []
root = 0
for i in range(N):
    nums = list(map(int, input().strip().split()))
    if nums[-1] == -1:
        root = i
    else:
        nums[-1] -= 1
    data.append(nums)

# 构建字典保存父节点和其子节点 ###########################################################
nodes_sons = {}
v = []
w = []
for son, line in enumerate(data):
    v.append(line[0])
    w.append(line[1])
    father = line[-1]
    if father not in nodes_sons:
        nodes_sons[father] = [son]
    else:
        nodes_sons[father].append(son)

# 动态规划 ###############################################################################
dp = [[0]*(V+1) for _ in range(N)]


def dfs(i, wi, vi):
    if i in nodes_sons:
        sons = nodes_sons[i]
        for son in sons:
            dfs(son, w[son], v[son])
            for j in range(V-vi, 0, -1):
                for k in range(0, j+1):
                    dp[i][j] = max(dp[i][j], dp[i][j-k]+dp[son][k])
    for j in range(V, vi-1, -1):
        dp[i][j] = dp[i][j-vi] + wi
    for j in range(vi):
        dp[i][j] = 0


dfs(root, w[root], v[root])
print(dp[root][V])