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.

azero0
  • 2,220
  • 3
  • 20
  • 31

2 Answers2

1

I know that this a NP-complete problem.

Not exactly, the partition optimisation problem is even known to be NP-hard.

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

NP-hard means just that there is no known algorithm (to determine the solution) performing better than the brute force method.

So you'll probably need an approximation, but which one fits your needs only you can know.

What is best algorithm for this?

Define "best".

Bergi
  • 630,263
  • 148
  • 957
  • 1,375
0

This is a variation of the famous problem of dividing the set of integers into two subsets whose sums are equal, or as nearly equals as possible. However, the problem you posed is even harder - you additionally have to check all combinations with one element removed from the original set.

Since the original problem is NP-complete, this one is also NP-complete (actually, this is the optimization version of the problem that is even NP-hard, as correctly mentioned in Bergi's answer). Good news is that even in this harder version the greedy approach can give you a satisfactory answer in most cases. The strategy is the following: take the greatest elements from the original set and put them in the first and second subset, one in each of them. Every other element from the original set put in the subset whose sum is smaller and repeat the procedure iteratively until you picked all elements.

To achieve the best result, you will need to repeat this procedure for all N subsets of the original set, where you obtain each subset by removing the element at index 1,2,...,N. This is what makes this problem even harder.

If you are interested in more advanced approach, have a look at Karmarkar-Karp differencing algorithm.

See also:

Miljen Mikic
  • 14,765
  • 8
  • 58
  • 66