如何使用动态规划求解树的最大权独立集（多解取节点最多）

树结构的最大权独立集本质是多叉结构上的DP，和线性路径的核心逻辑一致，仅需要遍历所有子节点累加状态即可，整体时间复杂度可以做到O(n)。 #

核心DP状态设计 #

每个节点存储两个状态，每个状态包含两个维度：(最大总权值, 对应最大节点数)：

• select[u]：选中当前节点u时，以u为根的子树能得到的最优结果
• not_select[u]：不选中当前节点u时，以u为根的子树能得到的最优结果

状态转移规则 #

状态比较优先级：先比较总权值，总权值大的状态更优；总权值相等时，节点数多的状态更优。

• 当选中u时，其所有子节点都不能被选中：

  select[u].总权 = weight[u] + sum( not_select[v].总权 for v in u的所有子节点 )
  select[u].节点数 = 1 + sum( not_select[v].节点数 for v in u的所有子节点 )
  

• 当不选中u时，每个子节点可以自由选择选或不选，取每个子节点的最优状态累加：

  对每个子节点v，取best_v = max(select[v], not_select[v]) （按上述优先级比较）
  not_select[u].总权 = sum( best_v.总权 for v in u的所有子节点 )
  not_select[u].节点数 = sum( best_v.节点数 for v in u的所有子节点 )
  

遍历与回溯步骤 #

1. 首先根据输入的edges数组构建无向邻接表，任选一个节点作为根节点（比如0号节点），执行后序DFS遍历，遍历过程中记录父节点避免重复访问，完成所有节点的状态计算。
2. 从根节点开始回溯构造结果集合：
   • 比较根节点的select[root]和not_select[root]，取更优的状态确定根节点是否被选中
   • 若当前节点被选中，则所有子节点都不能被选中，递归处理所有子节点的not_select状态
   • 若当前节点未被选中，则每个子节点取自身更优的状态，递归处理所有子节点对应的状态

复杂度说明 #

• 时间复杂度：每个节点和边仅被访问两次（一次DFS计算状态，一次回溯构造集合），整体为O(n)，符合要求
• 空间复杂度：递归栈+状态存储，整体为O(n)

参考实现代码 #

def max_weight_independent_set(n, edges, weight):
    # 构建无向邻接表
    adj = [[] for _ in range(n)]
    for u, v in edges:
        adj[u].append(v)
        adj[v].append(u)
    
    # 状态存储：每一项格式为(总权值, 节点数量)
    select = [(0, 0)] * n
    not_select = [(0, 0)] * n
    # 记录子节点的最优决策，方便回溯：child_decision[u]存(u的子节点v, v是否被选中)
    child_decision = [[] for _ in range(n)]

    def dfs(u, parent):
        select[u] = (weight[u], 1)
        not_select[u] = (0, 0)
        child_decision[u] = []
        for v in adj[u]:
            if v == parent:
                continue
            dfs(v, u)
            # 更新选中u的状态：子节点v必须不选
            s_w, s_cnt = select[u]
            ns_v_w, ns_v_cnt = not_select[v]
            select[u] = (s_w + ns_v_w, s_cnt + ns_v_cnt)
            # 选择子节点v的最优状态，更新不选u的状态
            sel_v_w, sel_v_cnt = select[v]
            if (sel_v_w > ns_v_w) or (sel_v_w == ns_v_w and sel_v_cnt > ns_v_cnt):
                best_w, best_cnt = sel_v_w, sel_v_cnt
                child_decision[u].append((v, True))
            else:
                best_w, best_cnt = ns_v_w, ns_v_cnt
                child_decision[u].append((v, False))
            # 累加不选u的状态值
            ns_u_w, ns_u_cnt = not_select[u]
            not_select[u] = (ns_u_w + best_w, ns_u_cnt + best_cnt)
    
    # 以0号节点为根执行DFS
    dfs(0, -1)
    res = []
    # 回溯构造结果集合
    def backtrack(u, parent, is_selected):
        if is_selected:
            res.append(u)
            # 子节点全部不能选
            for v in adj[u]:
                if v != parent:
                    backtrack(v, u, False)
        else:
            # 按之前记录的最优决策处理子节点
            for (v, sel) in child_decision[u]:
                backtrack(v, u, sel)
    
    # 确定根节点的选择
    root_s_w, root_s_cnt = select[0]
    root_ns_w, root_ns_cnt = not_select[0]
    if (root_s_w > root_ns_w) or (root_s_w == root_ns_w and root_s_cnt > root_ns_cnt):
        backtrack(0, -1, True)
    else:
        backtrack(0, -1, False)
    
    return res

内容的提问来源于stack exchange，提问作者Rita Doumit