路径图的最大权重独立集问题
Maximum-weight independent set problem for a path graph
在做Algorithms: Design and Analysis IIclass的时候，其中一题问的是路径图的最大权独立集问题。下面显示的是问题陈述的（模糊）屏幕截图，相应的讲座视频在 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 不正确。由于该算法会查看所有顶点，因此这两个选项似乎也应该是正确的。
the algorithm never selects the minimum-weight vertex.
考虑：**3-100-4-1-5-100-6
选择最小值 1 是有意义的，因为我们要选择两个 100's
The algorithm always selects the maximum-weight vertex.
考虑：5-99-100-99-7
排除最大值以支持到 99 是有意义的
对于这两个示例，请尝试查看该算法的作用及其工作原理。
推理这些类型问题的一个好方法是尝试 (0,0,0,1,1,1,2,2,2,3,3,3,99,99, 99,100,100,100) 它应该给你大部分的可能性。
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的最优解中，因为它的前一个顶点是"heavier"，并且由于所有权重都是正的，所以下一个权重的和而较重的顶点肯定大于7。因此，选项4不正确。
选项3正确。这是归纳法，因为子问题的最优解仅取决于前两个子问题的解。
在做Algorithms: Design and Analysis IIclass的时候，其中一题问的是路径图的最大权独立集问题。下面显示的是问题陈述的（模糊）屏幕截图，相应的讲座视频在 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 不正确。由于该算法会查看所有顶点，因此这两个选项似乎也应该是正确的。
the algorithm never selects the minimum-weight vertex.
考虑：**3-100-4-1-5-100-6 选择最小值 1 是有意义的，因为我们要选择两个 100's
The algorithm always selects the maximum-weight vertex.
考虑：5-99-100-99-7
排除最大值以支持到 99 是有意义的
对于这两个示例，请尝试查看该算法的作用及其工作原理。
推理这些类型问题的一个好方法是尝试 (0,0,0,1,1,1,2,2,2,3,3,3,99,99, 99,100,100,100) 它应该给你大部分的可能性。
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的最优解中，因为它的前一个顶点是"heavier"，并且由于所有权重都是正的，所以下一个权重的和而较重的顶点肯定大于7。因此，选项4不正确。
选项3正确。这是归纳法，因为子问题的最优解仅取决于前两个子问题的解。