Как решить логическую математическую задачу на PHP?

Question

[denis_druid]

Привет. Помогите выбрать алгоритм решения.
Задача:
Есть массив с N элементами (натуральные рандомные числа от 1 до 3 000).
Нужно сгруппировать элементы массива в 8 групп так, чтобы сумма элементов в каждой группе была максимально приближена к сумме элементов в любой группе. (Максимально приближены к равенству между собой)

В идеале в задаче n-групп. Восемь - это в моём конкретном примере.

Answer 1

[Arman]

Можно попробовать:
1. Найти N
2. Посчитать сумму всех элементом
3. Найти среднее на 8 групп
4. Отсортировать по возрастанию
5. Начать заполнять каждый массив, пока сумма в тек группе меньше среднего (пункт 3)

Comments

[longclaps]

Попробуй.

N = 8
data = [1, 2, 4, 8, 16, 32, 64, 128]

[denis_druid]

А если один или несколько элементов начального массива больше среднего?

[Arman]

denis_druid, в задаче нет для них условий, поэтому они будут одни в группе

Answer 2

[YURIY KOZLOV]

1. Находишь сумму всех чисел, и делишь на 8, получаешь целевое значение, обозначим его О
2. Идя с начала исходного массива заполняешь числами первый массив результата до тех пор, пока добавление следующего числа не даст сумму массива, большую, чем О
3. Повторяешь предыдущий шаг для остальных семи массивов.
4. Если в исходном массиве остались числа - добавляешь их по одному к выходным массивам, начиная с первого.
5. (Тут для удобства можно отсортировать результирующие массивы)
6. Выбираешь два массива - один с самым большим превышением О, другой с самой большой недостачей до О.
7. В первом (из этих двух) массиве выбираешь максимальное число, меньшее, чем превышение, и переносишь его во второй из этих двух массивов.
8. Повторяешь шаги 6 и 7 до тех пор, пока не окажется, что нет числа для переноса.
9. Конец.

Думаю, должно сработать.

Comments

[Дмитрий Добрышин]

для случая, когда N=8 и ряда степени 2 этим алгоритмом не получится 8 массивов.

[YURIY KOZLOV]

Дмитрий Добрышин, Да, такой крайний вариант я не проверил. Хотя те недостатки, что я, здесь вижу, устранить не сложно.

[denis_druid]

Дмитрий Добрышин, YURIY KOZLOV, Ребята, в идеале в задаче n-групп. Восемь - это в моём конкретном примере.

[YURIY KOZLOV]

denis_druid, да, это я помню :)) но перейти от от 8 к n в предложении мной алгоритме - дело пяти минут.... Если он заработает, конечно, при 8 :))))

Answer 3

[denis_druid]

Есть нечто похожее вот тут: ссылка

Comments

[YURIY KOZLOV]

Вы смогли то, что там описано, адаптировать к своей задаче?

[denis_druid]

YURIY KOZLOV,
Я пошел несколько другим путем.
Беру первые максимальные 8 чисел и записываю их в массив 1.
Остальные пишу в массив 2. и сортирую по убыванию.
Затем последний элемент (минимальный) из М2 добавляю к последнему (наименьшему) элементу М1. Сортирую. Повторяю, пока в М2 есть элементы.
Что-то похожее на то, что надо - получается.

[YURIY KOZLOV]

denis_druid, кажется, я что-то не понял в Вашем описании :) Вам же вроде бы нужно было на восемь групп разбить?

[denis_druid]

YURIY KOZLOV, да, восемь. Массив 1 (из моего примера) имеет 8 элементов. Возможно плохо описал.

Беру первые максимальные 8 чисел и записываю их в массив 1.

тут получается 8 элементов массива, 8 групп. Больше новые не добавляются, только суммируются числа.

[YURIY KOZLOV]

denis_druid, а, понял :))
мне кажется, такой вариант не очень хорош в том плане, что если не удалось с ходу получить хорошее распределение ние, то его уже не исправишь, т.к. не известно, что куда добавлялось.
Второй момент - я думал, что нужно получить группы чисел, а не только их суммы.
Третье - по алгоритму. Если действовать по схеме "минимальный добавляю к минимальному", то у Вас в конце останется максимальные числа во втором массиве.... Если они и так далеко выше среднего значения, то мне кажется результат будет не очень хороший...

[denis_druid]

Привет. Почему, неизвестно, что куда добавлялось? Можем отследить же в цикле. По поводу групп: мы и группы можем получить и суммы. Сути это не меняет, одно и то же.
Я немного изменил алгоритм, теперь работает по принципу к "наименьшему добавляет максимальное". Результат похож на то, что нужно. Ниже приведу пример с результатом.
----------------
Входящие данные, массив чисел:

1807
1751
1175
571
551
473
414
329
310
299
288
285
285
282
273
252
205
155
122
120
104
93
80
72
71
69
62
56
51
47
33
24
21
17
13
12
10
7
6
4

Выбираем 8 максимальных и назовем его Array1, оставшиеся элементы запишем в новый Array2.
Теперь запускаем цикл, в котором:
К минимальному значению Array1 добавляем максимальное значение Array2. Сортируем, повторяем, пока Array2>0.
--------
Результат:

1807
1751
1218
1206
1205
1205
1204
1203

Answer 4

[Alexej Simakov]

См.: Задача разбиения множества чисел

Comments

[denis_druid]

Спасибо, выше я уже давал ссылку на эту статью.