动态规划——循环最大加权独立集
Dynamic Programming - Circular Maximum Weighted Independent Set
我了解 MWIS 算法及其子问题
A[i]=max(A[i-1], A[i-2]+W[i])
但是当它加上使序列循环的条件时，意味着第一个元素连接到最后一个节点。
我卡住了，无法找出正确的子问题..
答案其实很简单。假设您在 A 中有一个节点权重列表，其中 A[i] 连接到 A[i-1] 和 A[i+1]。
还假设您有一个函数 solve() 可以解决第一个和最后一个节点 未 连接的 MWIS 问题。
循环变化的唯一附加条件是，如果第一个节点在集合中，则最后一个节点不能在其中。如果最后一个节点在集合中，则第一个节点不能在其中。
因此答案只是solve(A[1:])（没有第一个节点的数组的解决方案）和solve(A[:-1])（没有最后一个节点的数组的解决方案）的最大值。
为什么这是正确的？考虑最佳答案。它必须缺少 A[0] 或 A[-1]，因此它必须是 A[1:] 或 A[:-1].
的子集
我了解 MWIS 算法及其子问题
A[i]=max(A[i-1], A[i-2]+W[i])
但是当它加上使序列循环的条件时，意味着第一个元素连接到最后一个节点。
我卡住了，无法找出正确的子问题..
答案其实很简单。假设您在 A 中有一个节点权重列表，其中 A[i] 连接到 A[i-1] 和 A[i+1]。
还假设您有一个函数 solve() 可以解决第一个和最后一个节点 未 连接的 MWIS 问题。
循环变化的唯一附加条件是，如果第一个节点在集合中，则最后一个节点不能在其中。如果最后一个节点在集合中，则第一个节点不能在其中。
因此答案只是solve(A[1:])（没有第一个节点的数组的解决方案）和solve(A[:-1])（没有最后一个节点的数组的解决方案）的最大值。
为什么这是正确的？考虑最佳答案。它必须缺少 A[0] 或 A[-1]，因此它必须是 A[1:] 或 A[:-1].