个人中心
文章发布
退出
作者热门文章
- html - 出于某种原因，IE8 对我的 Sass 文件中继承的 html5 CSS 不友好？
- JMeter 在响应断言中使用 span 标签的问题
- html - 在 :hover and :active? 上具有不同效果的 CSS 动画
- html - 相对于居中的 html 内容固定的 CSS 重复背景？
26
4
假设我们有一个类似于链表(或有向无环图)的图。独立集由不与集中的任何其他节点共享边的节点组成。如果每个节点都被加权，我们如何计算独立节点集的最大可能值？我知道我们必须使用动态规划，所以我有一点线索，但我希望有人能解释他们将如何处理它。谢谢!
最佳答案
我认为这个问题对于任意有向无环图是 NP-hard 问题。已知无向图的相应问题是 NP-hard 问题，并且可以通过以使生成的图成为 DAG 的方式引导所有边，将该问题转换为问题的有向版本。原始图中的任何独立集都将是有向图中的独立集，反之亦然，因此对有向情况的任何解决方案都将解决无向情况。
你的问题是关于在链表上解决这个问题。如果您只是解决链表的问题，可以使用动态规划的多项式时间解决方案。提示一下，如果你选择链表中的一个节点，你必须跳过下一个节点，然后应该最大化剩下的。如果你不选择节点，你只是最大化列表其余部分的值。从这两个选项中取其优者并评估这种自下而上的方法将为您提供真正快速的 DP 算法。
希望这对您有所帮助!
关于dynamic-programming - 如何找到有向无环图的最大独立集？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/26455583/
26
4
0
我如何使用 CQLINQ 获取当前方法的输入参数集合？有像“参数”或“参数”这样的集合，只有“NbParamenter”不适合我的目的。 最佳答案 事实上，CQLinq 还没有这个功能。但是，在许多情
我想知道是否有人知道我的 makefile 中独立的 @ 符号和“dir”命令在这里(第二行和第三行)的作用: $(BUILD)/%.o: %.cpp @mkdir -p $(dir $@)
我想知道是否有人知道我的 makefile 中独立的 @ 符号和“dir”命令在这里(第二行和第三行)的作用: $(BUILD)/%.o: %.cpp @mkdir -p $(dir $@)
我的机器上有带有 4 个 cpu 的 Ubuntu 14.04(nproc 恢复了 4 个)。我安装并执行 Spark Standalone 后(本地)，我可以自己定义不同数量的奴隶。例如我想要有4个
我看到所有这些 iPhone 应用程序都带有内置的独立 webDav 服务器。是否有可以集成到现有应用程序中的独立(如在其自己的 IIS 中)C# webDAV 项目。 最佳答案 至少有两个用于 .N
我如何在独立的 Django 应用程序上进行迁移(即不属于任何项目的应用程序)。 例如在以下之后:https://docs.djangoproject.com/en/1.8/intro/reusabl
我目前正在使用 tortoiseSVN 对本地编程文件进行版本控制。我不运行 SVN 服务器，因为可以直接使用 tortoiseSVN(例如 http://invalidlogic.com/2006/
我有一些 Bootstrap 代码，当用户查看它时，它可以很好地为进度条部分设置动画。 然而它动画 全部 页面中的进度条而不是动画仅限 该查看部分中的进度条。结果，当用户转到进度条的另一部分时，这些已
我认为我们在 iOS 13.2/13.3 中发现了关于在独立模式下运行的 PWA 的回归。 由于在 iOS PWA 上无法访问 getUserMedia() 我们依赖 capture HTML5 输入
我有一个每周从系统运行一次的报告，并将数据导出到 Excel 文档中。我已经设置了将数据导出到 Excel 的工具，以便在格式化方面做得很好，但是一旦数据进入 Excel，我还需要做更多的事情。 是否
//值数组的格式为 { "var1", "val1", "var2", "val2",.. } public static String replaceMethod(String template,
当我在 eclipse 中运行我的项目时，它工作正常，当我将它导出为独立 jar 时，它会滞后。我使用相同的 vmargs，在 Eclipse 中尝试了 3 种不同的导出设置，似乎没有任何帮助 最佳答
我了解到 Java EE 中我非常喜欢的注释基础配置(@Resource)功能。然后我注意到注释实际上是 Java SE 的一部分。 所以我想知道是否可以将它与 Java SE 一起使用。我当然可以在
我无法理解为什么这种关系没有被持久化，并且程序不会正常退出，但在 Eclipse 中继续运行。 下面是我的代码，排除了包名: 主要: import java.io.BufferedInputStrea
我有一个在 Linux + Java 6 上运行的独立 Java 应用程序，它似乎被卡住了(没有生成日志)我如何在不使用任何其他工具(例如 jstack)的情况下获取此线程转储 尝试了以下命令，但它们
我正在非节点环境中构建应用程序，但我想利用 Babel 的 ES6 转译，以便我可以编写更好的代码并且仍然支持 IE11。 所以我继续包含在这里找到的独立文件: https://github.com/
扩展我对 MySQL 的理解。 1) 是否需要 64 位帮助？我是安装还是单独使用？ 2) 如果我打算在 MySQL Community Service 中使用 64 位，它会影响仅提供 32 位的
我有一个独立的 Java 应用程序，我必须为其集成一个规则引擎。我应该使用属性文件或 XML 文件定义规则。我需要规则引擎来读取属性或 XML 文件中定义的这些规则，并相应地在应用程序中实现代码。 任
我是wiremock新手，我正在尝试使用它来记录我负责集成测试的java应用程序的请求和响应。 我知道我的命令将类似于: java -jar wiremock-1.57-standalone.jar
我到处寻找我的问题的解决方案，但我的问题有点具体...我需要有关如何创建独立 radioGroup 列表的建议，例如图示: o item1 • item1' • item2 或 item2' o it
我是一名优秀的程序员,十分优秀！