Другие языки программирования и технологии

Разделить массив с числами на несколько массивов, чтобы сумма чисел в массивах была равна.

Например, есть самый простой массив - [0, 1, 2, 3, 4, 5]
И, скажем, его нужно разделить на 3 массива. Но так, чтобы сумма чисел в получившихся массивах везде была либо равна, либо максимально близкая. В данном случае идеально будет так:
[0, 5]
[4, 1]
[3, 2]
В каждом массиве сумма чисел равна 6.

А есть какая-нибудь формула, по которой можно было бы так поделить массив? Заранее спасибо!
PS: На каком языке - не важно.
Bekzhan Adilzhanov
Bekzhan Adilzhanov
518
Тут не формула нужна, а алгоритм нужен.
Для такого общего случая, когда элементы массива являются арифметической
прогрессией, можно искать элементы новых массивов как
min(mass)+max(mass). Затем исключать найденные числа из массива и
продолжать операцию. Для таких массивов это подойдет на 100 %.

Что касается для алгоритма общего случая, попробую составить:
Найдем, на какие числа n делится без остатка и чему равен результат деления. n - размерность первоначального массива. Те числа, на которые делится n - размерность новых массивов, результат деления - число новых массивов.
предположим, что массив отсортирован по убыванию.
Тогда заполним первые элементы новых массивов элементами из начального массива, начиная с нулевого элемента.
Результат: (при первоначальном массиве: 39 34 33 25 16 11 9 3 1)
[39
[34
[33
Затем, повторим эту операцию, только заполнять массивы будем снизу вверх
[39 11 = 50
[34 16 = 50
[33 25 = 58
далее находим новый массив с наименьшей суммой и добавляем ему максимальный элемент из оставшихся и т. д.
[39 11 9 ] = 59
[34 16 3 ] = 53
[33 25 1 ] = 59
Думаю, это максимально приближенный результат к условию задачи.
Роман Шилков
Роман Шилков
4 504
Лучший ответ
Это чето типа похоже на "задачу укладки рюкзака". Эта задача уже давно решена, поищите в нете, может подойдут те же алгоритмы.
Первое что пришло на ум: складываем все числа в массиве и делим на количество новых массивов. получаем число, к которому должны стремиться суммы новых массивов. Далее перебираем старый массив, пробегаемся по нему и добавляем числа из исходноо так чтобы подогнать к нужной сумме
Oscar Nyambe
Oscar Nyambe
673
Роман Шилков это подойдет, если новые массивы состоят из двух элементов
Роман Шилков мое замечание ошибочно. Дополню ответ: необходимо сравнивать получившееся число после деления с максимальным элементом массива. Если оно меньше максимального, то необходимо сокращать количество новых массивов и, соответственно, увеличивать число элементов в новых массивах
Роман Шилков если для приведенного примера: 5 4 3 2 1 0 делить на два массива, то по приведенному мной алгоритму получится:
[5
[4
затем
[5 2
[4 3
след. шаг:
проверяем сумму, если сумма у первого массива меньше либо равна сумме эл-ов 2го массива, то заполнение идет с первого массива.
7=7
значит следующим будет заполнятся первый массив
[5 2 1]
[4 3 0]