如何理解背包问题是NP完全的？
如何理解背包问题是NP完全的？
提问于 2010-10-11 23:17:57
我们知道背包问题可以用动态规划在O(nW)复杂度内解决。但是我们说这是一个NP完全问题。我觉得在这里很难理解。
(n是项目的数量。W是最大音量。)
回答 3
Stack Overflow用户
发布于 2010-10-11 23:23:08
这完全取决于您在O(...)中放入了哪些参数。
如果目标权重受到number W的限制，那么正如您所提到的，问题具有O(n*W)复杂性。
但是如果权重太大，并且你需要复杂度独立于W的算法，那么问题就是NP-complete。(在最简单的实现中是O(2^n*n))。
Stack Overflow用户
发布于 2010-10-11 23:47:35
你可以阅读这个简短的解释：The NP-Completeness of Knapsack。
Stack Overflow用户
发布于 2010-10-11 23:25:38
要理解NP-completeness，您必须学习一些复杂性理论。然而，基本上，它是NP完全的，因为背包问题的有效算法也是SAT，TSP和其他问题的有效算法。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/3907545
复制相关文章
相似问题
腾讯云开发者
