3

You can exempt atmost one element from the set to acheive the goal. example:-

N=3

the numbers given are = 1,2,5

So,

Set 1 should be :- [1]

Set 2 should be :- [2]

We have excluded 5 as we can acheive a lesser difference without it being in either groups.

N=4

numbers = 1,2,2,5

Set1 = [1,2,2]

Set2 = [5]

What is best algorithm for this? I know that this a NP-complete problem. And I think that brute force would give me the correct solution but I need an algorithm if available.

4

2 回答 2

1

我知道这是一个 NP 完全问题。

不完全是，分区优化问题甚至被认为是 NP 难的。

而且我认为蛮力会给我正确的解决方案，但如果有的话，我需要一个算法。

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

因此，您可能需要一个近似值，但只有您知道哪个适合您的需求。

什么是最好的算法？

定义“最佳”。

于 2015-02-07T10:32:18.383 回答
0

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

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

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

如果您对更高级的方法感兴趣，请查看Karmarkar-Karp 差分算法。

也可以看看：

于 2015-02-07T10:31:26.363 回答