algorithm - 路径图的最大权重独立集问题

Question

同时采取Algorithms: Design and Analysis II类中，其中一个问题询问路径图的最大权重独立集问题。下面显示的是问题陈述的(模糊)屏幕截图，相应的讲座视频位于 YouTube 上:

https://www.youtube.com/watch?v=0awkct8SkxA

https://www.youtube.com/watch?v=pLOkbHGRsv0

https://www.youtube.com/watch?v=Im_zjFkZDCY

这个问题可以通过动态编程优雅地解决，只需一行代码。

a[i] = max(a[i - 1], a[i - 2] + w[i])

问题如下:

Which of the following is true for our dynamic programming algorithm for computing a maximum-weight independent set of a path graph? (Assume there are no ties.)

• As long as the input graph has at least two vertices, the algorithm never selects the minimum-weight vertex.
• The algorithm always selects the maximum-weight vertex.
• If a vertex is excluded from the optimal solution of two consecutive subproblems, then it is excluded from the optimal solutions of all bigger subproblems.
• If a vertex is excluded from the optimal solution of a subproblem, then it is excluded from the optimal solutions of all bigger subproblems.

事实证明，正确答案是#3，这有点直观，因为子问题的最优解仅取决于前两个子问题的解。但我不清楚为什么选项 1 和 2 不正确。由于该算法会查看所有顶点，因此这两个选项似乎也应该是正确的。

Answer 1

OP:为了完整起见，这是一个完整的答案，灵感来自 @robert-king 的答案。

考虑路径10-2-1-4。该算法选择的顶点为10, 1，其中选择最小值1。因此，选项1不正确。

考虑路径1-3-10-9。算法选择的顶点为3, 9，其中最大10未选择。因此，选项2不正确。

考虑路径1-9-7-1-5。算法选择的顶点是1,7,5。然而，7并未包含在子问题1-9-7的最优解中。请注意，7 也没有包含在子问题 1-9-7-1 的最优解中，因为它的前一个顶点“更重”，并且由于所有权重为正，下一个权重与较重顶点的总和肯定大于7。因此，选项4不正确。

选项3是正确的。这是归纳得出的，因为子问题的最优解仅取决于前两个子问题的解。