首页 文章

用于以 2 的幂进行集划分的多项式时间算法

提问于
浏览
2

与 programming/implementation 相比,这更是一个 algorithm/proof 问题,因此如果 StackOverflow 不是正确的选择,我们深表歉意。

至于问题:

假设我们有一组数字,并且每个数字都必须是一个正整数和2的幂。例如,也许我们有{1, 1, 2, 4, 8, 8, 8, 8, 128}。我们想将集合划分为AB,其中每个元素必须恰好在AB内,以使A的元素之和等于B的元素之和。是否有针对这种情况的多项式时间算法?

  • 确定甚至不存在分裂,或者

  • 返回到AB的分区,以使它们的总和相等?

当然,如果没有多项式时间算法,我很想知道证明该问题的一些方向(i.e.通过显示与另一个 NP-hard 问题的等效性)。

我知道有一些问题可能会有所帮助,就上下文而言,我将在这里进行总结:

  • Set-partition 是 NP-hard。在 set-partition 中,您有一组任意数字。解决方案是分区 A 和 B,其中每个元素都恰好在 A 或 B 中,例如sum(A) = sum(B)

  • Subset-sum 是 NP-hard。在 subset-sum 中,您有一组任意数字。解决方案是该集合的子集,以使子集元素的总和等于某个所需的数量 x。

任何帮助是极大的赞赏。谢谢!

1 回答

  • 3

    一种看待这种情况的方法是说您正在尝试将目标数字 total/2 表示为所提供数字的总和。这实际上只是进行更改的问题。

    这是一个有用的引理:如果您有一个硬币的集合,这些硬币的值都是值<= 2 ^ k 的 2 的幂,那么您可以精确地制作 2 ^ k,也不能制作任何大于或等于 2 ^ k。要看到这一点,请拿走所有硬币,如果您有多个相同价值的硬币,请将这两个硬币粘在一起,制成价值第二高的硬币,直到用完硬币或达到 2 ^ k。如果您达到 2 ^ k,您就完成了。如果用光了,您将拥有各种值的单个硬币的集合,这些硬币仍然是 2 的幂,都小于 2 ^ k,每个不同的值只有一个,因此结果加起来不能超过 2 ^ k-1 。

    现在,要更改目标值,请将数字当作硬币,然后反复放置最大的硬币,该硬币的数量不超过您到目前为止的值与目标值之间的差。

    如果达到目标值,则解决问题。如果没有,您错过了正确的答案吗?您从最大的硬币开始。寻找您的第一个错误-您拿了一个 2 ^ k 大小的硬币,有某种方法可以弥补不包括 2 ^ k 大小的硬币的余额。但是,这种神奇的方法是使用不超过 2 ^ k 的硬币来弥补超过 2 ^ k 的零钱。因此,在这个正确答案中的某处,存在一组硬币,它们的总和恰好为 2 ^ k。采取这个正确的答案,取出加起来等于 2 ^ k 的硬币,并用您使用的 2 ^ k 硬币替换,您将获得另一个正确的答案-因此,您毕竟是对的,如果可以得到任何解决方案,则可以通过重复使用小于目标值距离的最大硬币(数字)来获得它。

    完好性检查-查看http://cs.mcgill.ca/~lyepre/pdf/assignment2-solutions/subsetSumNPCompleteness.pdf中给出的子集总和的减少量,请注意它要求的数字不是 2 的幂,因此我在这里提出的建议仅在数字为 2 的幂时才有效。在多项式时间内解决 NP-complete 问题。

相关问题