Search code examples
algorithmgraph-algorithmgenetic-algorithmstl-algorithmevolutionary-algorithm

Split Algorithm on C++

I have an array with 8 elements:

a[8] = {9, 7, 6, 2, 3, 1, 5, 4}

I want to divide 8 elements to 3 group. Each group is the sum of 1 or more element. The sum of each group is most similar.

Solution

  • You are describing the k-partition problem with k=3.

    Unfortunately, this problem is known to be (strong) NP-Hard, so there is no known efficient solution to it (and the general belied is one does not exist).

    Your best hope will be brute force search: create all partitions to 3 groups, and choose the best one out of them. If you are dealing with 8 elements - that should be possible, but it will quickly become too slow for larger arrays I am afraid.