将给定的一组数字N分成两组，使它们的和之差最小？

Question

您可以从集合中豁免至多一个元素以达到目标。 例如：

N=3

所给的数字为1、2、5。

因此，

Set 1 应该是：[1]

Set 2 应该是：[2]

我们排除了5，因为我们可以在不将其放入任何组的情况下达到更小的差异。

N=4

数字为1、2、2、5。

Set1=[1,2,2]

Set2=[5]

这个问题是NP完全问题，我知道暴力算法可以给出正确的解决方案，但如果有算法，我需要它。

- azero0

---

你的使用场景是否适合伪多项式时间？ - harold

Answer 1

我知道这是一个NP完全问题。 并不完全如此，分区优化问题甚至被认为是NP难的。

我认为暴力法会给我正确的解决方案，但如果有算法可用，我需要它。 NP难意味着没有已知的算法（确定解决方案）比暴力方法更好。

因此，您可能需要一个近似算法，但只有您自己才知道哪个适合您的需求。

对于这个问题，最好的算法是什么？ “最好”的定义是什么？

- Bergi

Answer 2

这是将整数集合分成两个子集，使其和相等或尽可能接近的著名问题的变体。然而，你提出的问题更难 - 你还必须检查从原始集合中删除一个元素后的所有组合。

由于原始问题是NP完全问题，这个问题也是NP完全问题（实际上，这是该问题的优化版本，正如Bergi在回答中正确提到的那样，它甚至是NP难问题）。好消息是，在这个更困难的版本中，贪婪算法在大多数情况下都能给出令人满意的答案。策略如下：从原始集合中取出最大的元素，并将它们放入第一个和第二个子集中，每个子集一个。将原始集合中的其他元素放入和较小的子集中，并重复这个过程，直到选择完所有元素。

为了达到最佳结果，您需要对原始集合的所有N个子集重复这个过程，其中通过删除索引1、2、...、N处的元素获得每个子集。这就是这个问题变得更加困难的原因。

如果您对更高级的方法感兴趣，请参考Karmarkar-Karp差异算法。

另请参阅：

• 最简单的难题

- Miljen Mikic