blocks|key|2751289|text|the+algorithm+never+selects+the+minimum-weight+vertex.|type|code-block|depth|inlineStyleRanges|entityRanges|data|syntax|javascript|2751290|考虑：**3-100-4-+1+-1-5-100-6选择1是合理的，因为我们想选择两个100。|unstyled|2751291|The+algorithm+always+selects+the+maximum-weight+vertex.|2751292|考虑：5-99-100-99-7|offset|length|style|BOLD|2751293|这是有意义的，排除最大值，以支持到99年代。|2751294|对于这两个例子，试着看看算法会做什么以及它为什么工作。|2751295|对这些类型的问题进行推理的一种很好的方法是尝试(0,0,0,1,1,1,2,2,2,3,3,3,99,99,99,100,100,100)的所有排列，它应该会给你大部分的可能性。|2751296|entityMap^0|0|0|0|3|D|0|0|0|0^^$0|@$1|2|3|4|5|6|7|W|8|@]|9|@]|A|$B|C]]|$1|D|3|E|5|F|7|X|8|@]|9|@]|A|$]]|$1|G|3|H|5|6|7|Y|8|@]|9|@]|A|$B|C]]|$1|I|3|J|5|F|7|Z|8|@$K|10|L|11|M|N]]|9|@]|A|$]]|$1|O|3|P|5|F|7|12|8|@]|9|@]|A|$]]|$1|Q|3|R|5|F|7|13|8|@]|9|@]|A|$]]|$1|S|3|T|5|F|7|14|8|@]|9|@]|A|$]]|$1|U|3|-4|5|F|7|15|8|@]|9|@]|A|$]]]|V|$]]

<pre><code>the algorithm never selects the minimum-weight vertex.
</code></pre>

Consider: **3-100-4-1-5-100-6
it makes sense to choose 1, the minimum, since we want to choose the two 100's

<pre><code>The algorithm always selects the maximum-weight vertex.
</code></pre>

Consider: 5-99-100-99-7

It makes sense to exclude the maximum in favour of the to 99's

For both these examples, try see what the algorithm would do and why it works.

A good way of reasoning about these types of problems is to try all permutations of (0,0,0,1,1,1,2,2,2,3,3,3,99,99,99,100,100,100) and it should give you most of the posibilities.

blocks|key|768536|text|在这里:这是一个完整的完整的答案，灵感来自@robert-king的答案。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|768537|考虑路径10-2-1-4。算法选择的顶点是10,+1，其中选择了最小的1。因此，备选案文1是不正确的。|offset|length|style|CODE|768538|考虑路径1-3-10-9。算法选择的顶点是3,+9，其中没有选择最大10。因此，备选案文2是不正确的。|768539|考虑路径1-9-7-1-5。算法选择的顶点为1,+7,+5。然而，7不包括在子问题1-9-7的最优解中。注意，7也没有包含在子问题1-9-7-1的最优解中，因为它的前一个顶点是“更重的”，而且由于所有的权重都是正的，所以下一个权重和较重的顶点的和肯定大于7。因此，备选案文4是不正确的。|768540|备选案文3是正确的。这源于归纳法，因为子问题的最优解只取决于前两个子问题的解。|768541|entityMap^0|0|4|8|L|5|Z|1|0|4|8|L|4|Y|2|0|4|9|M|7|X|1|15|5|1J|1|1T|7|3J|1|0|0^^$0|@$1|2|3|4|5|6|7|P|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|Q|8|@$D|R|E|S|F|G]|$D|T|E|U|F|G]|$D|V|E|W|F|G]]|9|@]|A|$]]|$1|H|3|I|5|6|7|X|8|@$D|Y|E|Z|F|G]|$D|10|E|11|F|G]|$D|12|E|13|F|G]]|9|@]|A|$]]|$1|J|3|K|5|6|7|14|8|@$D|15|E|16|F|G]|$D|17|E|18|F|G]|$D|19|E|1A|F|G]|$D|1B|E|1C|F|G]|$D|1D|E|1E|F|G]|$D|1F|E|1G|F|G]|$D|1H|E|1I|F|G]]|9|@]|A|$]]|$1|L|3|M|5|6|7|1J|8|@]|9|@]|A|$]]|$1|N|3|-4|5|6|7|1K|8|@]|9|@]|A|$]]]|O|$]]

OP here: Here's a full answer for completeness sake, inspired by @robert-king's answer.

Consider the path <code>10-2-1-4</code>. The vertices selected by the algorithm are <code>10, 1</code>, where <code>1</code>, the minimum, is selected. Thus, option 1 is incorrect.

Consider the path <code>1-3-10-9</code>. The vertices selected by the algorithm are <code>3, 9</code>, where the maximum <code>10</code> isn't selected. Thus, option 2 is incorrect.

Consider the path <code>1-9-7-1-5</code>. The vertices selected by the algorithm are <code>1, 7, 5</code>. However, <code>7</code> was not included in the optimal solution of the subproblem <code>1-9-7</code>. Note that, <code>7</code> was not included in the optimal solution of the subproblem <code>1-9-7-1</code> either, because the its previous vertex was "heavier", and since all weights are positive, the sum of the next weight and the heavier vertex is certainly greater than <code>7</code>. Thus, option 4 is incorrect.

Option 3 is correct. This follows from induction, since the optimal solution to a subproblem depends only on the solutions of the previous two subproblems.

While taking the <a href="https://lagunita.stanford.edu/courses/course-v1:Engineering+Algorithms2+SelfPaced/about" rel="nofollow noreferrer">Algorithms: Design and Analysis II</a> class, one of the questions asks about the maximum-weight independent set problem for a path graph. shown below is a (blurry) screenshot of the problem statement, and the corresponding lecture videos are on YouTube:

<a href="https://www.youtube.com/watch?v=0awkct8SkxA" rel="nofollow noreferrer">https://www.youtube.com/watch?v=0awkct8SkxA</a>

<a href="https://www.youtube.com/watch?v=pLOkbHGRsv0" rel="nofollow noreferrer">https://www.youtube.com/watch?v=pLOkbHGRsv0</a>

<a href="https://www.youtube.com/watch?v=Im_zjFkZDCY" rel="nofollow noreferrer">https://www.youtube.com/watch?v=Im_zjFkZDCY</a>
<a href="https://i.stack.imgur.com/HMQ9a.jpg" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/HMQ9a.jpg" alt="enter image description here"></a>

This problem can be elegantly solved by dynamic programming, with literally one line of code.

<pre><code>a[i] = max(a[i - 1], a[i - 2] + w[i])
</code></pre>

The question is as follows:

<blockquote>
 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.)
 
 <ul>
 <li>As long as the input graph has at least two vertices, the algorithm never selects the minimum-weight vertex.</li>
 <li>The algorithm always selects the maximum-weight vertex.</li>
 <li>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.</li>
 <li>If a vertex is excluded from the optimal solution of a subproblem, then it is excluded from the optimal solutions of all bigger
 subproblems.</li>
 </ul>
</blockquote>

Turns out, the correct answer is #3, which is somewhat intuitive, since the optimal solution to a subproblem depends only on the solutions of the previous two subproblems. But it's not clear to me why options 1 and 2 are incorrect. Since the algorithm looks at all the vertices, it seems both of those options should be correct too.

Maximum-weight independent set problem for a path graph

翻译质量差，导致语言生硬或混乱。

没有提供实际的解决方法或示例。

解答不清晰，无法理解或解决问题。

页面排版不美观，阅读体验差。

文章

问答

视频

学习中心

腾讯云实验室

直播

竞赛

腾讯云代码分析专区

腾讯iOA零信任安全管理系统专区

腾讯云架构师技术同盟交流圈

腾讯云数据库专区

腾讯云顾问专区

腾讯云原生专区

腾讯混元专区

腾讯云TCE专区

腾讯云Lighthouse专区

腾讯云HAI专区

腾讯云Edgeone专区

腾讯云存储专区

腾讯云智能专区

腾讯轻联专区 

腾讯云开发专区

TAPD专区

腾讯轻量云游戏服专区

腾讯云最具价值专家

腾讯云架构师技术同盟

腾讯云创作之星

腾讯云开发者先锋

腾讯云代码助手

云原生构建

TAPD 敏捷项目管理

Cloud Studio

SDK中心

API中心

命令行工具

涵盖代码开发、场景应用、自动测试全流程，助你从零构建专属AI助手

一站式MCP教程库，解锁AI应用新玩法

在使用类时，其中一个问题询问路径图的最大权重独立集问题。下面显示的是问题陈述的(模糊)屏幕截图，相应的讲座视频在YouTube上显示：​这个问题可以通过动态编程巧妙地解决，只需一行代码即可。a[i] = max(a[i - 1], a[i - 2] + w[i])问题如下：对于我们计算路径图的最大权独立集的动态规划算法...

问路径图的最大权无关集问题
EN

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问路径图的最大权无关集问题EN

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问路径图的最大权无关集问题
EN