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

Question

您最多可以从集合中排除一个元素以实现目标。 示例:-

N=3

给出的数字是 1,2,5

所以，

第 1 组应该是:- [1]

第 2 组应该是:- [2]

我们排除了 5 个，因为我们可以在不属于任何一组的情况下实现较小的差异。

N=4

数字 = 1,2,2,5

集合 1 = [1,2,2]

组 2 = [5]

最好的算法是什么？ 我知道这是一个 NP 完全问题。 我认为蛮力会给我正确的解决方案，但如果可用的话，我需要一个算法。

Answer 1

I know that this a NP-complete problem.

不完全是，partition optimisation problem甚至已知是 NP 难的。

And I think that brute force would give me the correct solution but I need an algorithm if available.

NP-hard 意味着没有已知算法(确定解决方案)比蛮力法表现得更好。

所以你可能需要一个 approximation ，但只有您知道哪一个适合您的需求。

What is best algorithm for this?

定义“最佳”。