How to divide an array into two equal parts, the sum of the elements of which are closest to equality.

How to divide an array into two parts, I know. But can not figure out how to do? so that the sums of the elements of these two parts are equal. Please prompt the algorithm.

For those who asked to clarify the condition: the array is divided into two equal parts, the number of elements of the first part = the number of elements of the second. Also, the sum of the elements of the first part is equal to or closest to the equality of the second part.

  • And what if you can not be equal parts, how not to divide? Can you move items? - Dex
  • the incoming array must be even. You can move - ArniLand
  • Do you need the algorithm itself or how to do it in a specific language? - Deonis
  • I need to implement on C # - ArniLand
  • one
    @Merlin both) - rasmisha pm

7 answers 7

  • 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.
  • 2
    But they ask that A and B be of equal size. This algorithm does not work that way. - avp
  • one
    avp, do not ask, I also considered the option with equal halves .. and by the way, if the difference is not divided by 2, but the array is not divided into equal parts .. - Gorets
  • one
    @avp, I think that the vehicle, speaking of equality, meant not equal in size arrays, but still equal in sum of values. But it would be nice if the author himself specified. - Deonis
  • one
    @Deonis for some reason I also thought about equality in the size of arrays. - rasmisha
  • 2
    In the title of the question , two equal parts are written , the sum of the elements of which are closest to equality - avp

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.

  • one
    Something I also doubt) In my opinion this is a task about a backpack, where the cost of each element is 1, weight is an element. And the capacity is half the amount of the array. As soon as we find a solution costing n / 2 (where n is the number of elements in the array), we stop and restore the array. Although maybe I just need to sleep (also not sure) :) - rasmisha
  • Well, if the option that was suggested by @ Kotik_hohet_kushat is plus, the algorithm is still the right one, since almost identical - Deonis
  • Too (like @ Kitty) is not that. The algorithm does not provide equal size parts. This is (one of the conditions of the question) and a snag. - avp
  • @avp, posted above)) - Deonis
  • @Deonis Are you talking about your algorithm? - rasmisha

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)

  • @rasmisha - Sorry to erase my last comment under my answer, just pondering over the proof that this is an NPC task. - Not sure, by the way, that ff, in which the metric of goodness is proportional to the deviation from a half-sum, is a good choice. Although not very strong in genetic algorithms. - Costantino Rupert
  • one
    @ Kitty at the expense of ff may well be. Just decided to share the option that came to mind and seemed one way to find an approximate answer. - rasmisha
  • @ Kitty by the way, the first idea (I don’t know how correct it is) exactly coincides with yours (at least judging by the links given by you), but I’m not sure again that I distributed the weight / cost / capacity correctly. - rasmisha
  • one
    @rasmisha - Yes, I, too, as soon as I looked at the question, I got the idea that, in fact, the two parts of the array are two backpacks with N / 2 elements each. But here it is not very clear how to strictly set limits for total weight. And the price of lax statements when working with algorithms is known to everyone :) - Maybe there are some other formulations of the Knapsack Problem , which are better suited for this case, did not check. - Costantino Rupert

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.

  • one
    - For [0,1,2,2,2,3,4,7,10,40,54,60,120,127] , the greed of the algorithm appears. - Your algorithm will return [127,54,10,7,4,3,2] and [120,60,40,0,1,2,2] , but you can get a smaller variation in the amounts, for example, change 54 and 60 places. - In general, it's cool that you didn’t have a chance to do it :) - Costantino Rupert
  • In general, some methods will work to some extent correctly, if the digit capacity of numbers is approximately the same, BUT if one number is significantly larger, then everything will disappear. That is even your example . ))) So, it's time to go to bed with a calm soul;) - Deonis
  • @Deonis In the example with 100500 algorithm just worked correctly - it returned the result with the smallest possible difference, so apparently with peace of mind will not work :) - Costantino Rupert
  • Hmm, yes) You can reduce greed by checking the increase in scatter for j == k-1. if the difference of the amounts increases when choosing the maximum elements, then swap them. It is likely that this will not be enough. The problem is interesting, yes. - Yura Ivanov
  • @Yura Ivanov have you not slept because of this? - rasmisha
  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

  • I think that points 1-4 should be slightly modified to search for the border in the array, where the difference between the sum of the elements of the parts changes its sign or is equal. - Dex
  • 5 times read. I did not understand points 6-8) - rasmisha
  • one
    @Gorets, then the question most likely arises what to do if: 1. The difference is not divisible by 2 completely 2. for the most part there is no this value 3. what to do if (7) is not divisible by 2 entirely 3. in the smaller part there is no this value - Dex
  • @Dex, maybe, but for now it seems to me that your algorithm is more difficult @rasmisha, added - Gorets
  • 3
    Not a bad attempt to come up with an algorithm for an NPC task :) - Costantino Rupert

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.
    • one
      The greedy algorithm, as already mentioned, will give an approximate result. - rasmisha
    • T. e. I just painted it in words? - Niki-Timofe
    • Well something similar at least - rasmisha
    • The design of the answer is lapped from the answers to @ Kotik_khohet_kushat - Specter
    • one
      > If my decision is not correct - do not minus XD I'm in the house! :-D The logical objection: And I am Mr. Neutron! - karmadro4