开发者社区

文档建议反馈控制台

文章/答案/技术大牛

发布

社区首页 >问答首页 >NP-完全还是NP-hard？

问NP-完全还是NP-hard？
EN

Stack Overflow用户

提问于 2016-05-06 12:14:01

回答 1查看 75关注 0票数 1

给定一个包含n个正整数(n为偶数)的列表，将该列表划分为两个子列表，使得这两个子列表中的整数之和的差值最小化。这是NP-完全问题还是NP-hard问题？

EN

回答 1

Stack Overflow用户

发布于 2016-09-18 06:19:56

TL;DR -这是np难题。

这是分区问题的优化版本。划分问题是决定一个给定的正整数列表是否可以被分成两个子集，以便这些子集的和相等。优化版本要求最小化差异(就像您要求的那样)。

划分问题是np完全的，但优化问题是np困难的。

你可以在wiki上阅读更多关于这些问题的内容：https://en.wikipedia.org/wiki/Partition_problem

票数 0

EN

页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://stackoverflow.com/questions/37064121

复制

相似问题