Splitting an array by the equality of two parts

• You reformulated the so-called Partition Problem . This is a well-known Weakly NP-Complete problem for which there exists a pseudopolynomial algorithm and an approximate polynomial algorithm.

You can read more by clicking on the first link, or, for example, here:

• If you are satisfied with the approximate solution, then use O(N log N) greedy algorithm

(For those who sit in the comments :)

• The condition of dividing the array into parts of the same length does not affect the NP completeness of the task (it is still NPC ). The proof of this fact from the point of view of the theory of algorithms may sound something like this:

• We reduce the general problem Partition Problem (PP) to a problem with two equal parts Equally Sized Partition Problem (ESPP) , that is, we show that ESPP includes the PP problem as a special case.

• Consider a sequence of elements of length 2k , of which k are zeros. Now, having solved this problem using the ESPP algorithm, we obtain two sequences of length k , the difference of the sums of which is minimal. Since zero elements do not change the sum, we can “overtake” them from one sequence to another, respectively, reducing the task to PP .

• Once we have proved that the problem is NPC , then there is no polynomial algorithm for solving this problem. You can use the pseudopolynomial algorithm from Wikipedia, adapting it for yourself or any greedy algorithm from those proposed below.

Continuing to my comments

In the title of the topic, you indicate that if they are not absolutely equal, then they are as close to equality as possible. Then, in PHP I did the following:

1. I counted the sum of the array values ​​and divided it into two
2. Sorted array descending values
3. Enumerating sorted massi

array_1 = 0;

array_m2 = 0;

if (sum of array1 <= sum of array2 || sum of array2> = gender of total_sum) {

 добавить значение в массив1 сумма_массива1 += значение; 

} otherwise {

 добавить значение в массив2 сумма_массива2 += значение; 

}

The code in PHP (you can check it here - http://writecodeonline.com/php/ ):

 $arr = array(10,68,30,28,34,74,52,20,176,18,86,14,22,4); // исходный массив rsort($arr,SORT_NUMERIC); // сортируем по значениям в обратном порядке $halfSum = intval(array_sum($arr) / 2); // высчитываем сумму значений и делим на две примерно равные части $arr_first = array(); // первый массив $arr_second = array(); // второй массив $sum1 = 0; // сумма первого массива для сравнения $sum2 = 0; // сумма второго массива для сравнения // перебираем отсортированный исходный массив foreach($arr as $val){ // сумма первого массива меньше второго // и сумма второго массива больше или равна половине общей суммы // то очередное значение добавляется в первый массив // в ином случае - во второй массив if($sum1 <= $sum2 || $sum2 >= $halfSum){ $arr_first[] = $val; $sum1 += $val; } else { $arr_second[] = $val; $sum2 += $val; } } //выводим суммы обоих массивов echo array_sum($arr_first).'<br />'.array_sum($arr_second); 

Of course, I’m far from sure that it works correctly, but I’ve tested it several times and it seems to have done everything perfectly.

As an option, you can offer a genetic algorithm.

FitnessFunction understands the amount (the closer to half the sum of all the elements of the array, the steeper)

A chromosome consists of an n / 2 gene (a gene is an element of an array).

Play around with the population quantity, see how much approximately it will be needed for a less or less adequate result. Well, think about how to cross (you can probably sort the genes in the parents and cyclically cross)

Again, the result will be approximate (to improve, you can run the algorithm several times and select the best result)

It seems to work :) For an array with an even number of elements. For an odd little need to correct, and lazy)

The essence of this. Sort the original array. We fill both output arrays at the same time one number in each. We add a larger number to an array with a smaller amount, add an element to an array with a larger amount, adding which will leave a larger array with a larger amount (starting to check with the smallest element, if it remains with a larger one, then the first element is added, etc. d.)

UPD The problem of greed manifests itself at the stage when the maximum elements are selected. When the maximum and one of the minimum elements are chosen, greed does not affect the choice. Accordingly, I propose branching this uncertainty. We find all the solution sets based on the fact that maximal elements can belong both to the first and second array, and to the second and first. And then we choose the most appropriate from the point of view of the minimal difference of the sums. In the worst case, it will be brute force, sorry.

1. look at the length of the array
2. look at the amount of halves
3. if equal - profit
4. if not, look at the difference and remember
5. divide the difference by 2
6. look for this value (difference / 2) in the part where there is more
7. divide it (difference / 4) by another 2 and look for this value (what happened) on the left side
8. we change them (what we found in the halves of the array) in places

the algorithm is estimated by the eye, mb wrong, check, correct and if not correct, forgive

You can run a binary search for the answer, and for each value check with the algorithm for a set of a backpack, can we type a backpack of this size. The complexity is O (N ** N logN). If there is an answer, it is found, and it is possible to modify it to search for two subarrays of minimal difference. This is an option.

1. Sort the array.
2. Take the sum of the values ​​of the extreme elements of the array and store them alternately in one of two variables.
3. If the array length is odd , add the value of the центрального element to the smaller of the two variables.