Ищем алгоритм для уникальной задачи

Question

У меня есть шесть массивов, каждый из которых имеет (не обязательно уникальное) значение от одного до пятидесяти. Мне также дают ряд предметов, которые можно разделить между ними. Значение каждого элемента определяется массивом, в котором он находится. Массивы могут содержать бесконечные или нулевые элементы, но сумма элементов во всех массивах должна равняться исходному количеству данных элементов.

Я хочу найти лучшая конфигурация элементов в массивах, где сумма значений элементов в каждом отдельном массиве максимально приближена друг к другу.

Например, предположим, что у меня есть три массива со значением 10 и три массива с значение 20. Для девяти элементов один будет go в каждом из массивов '20', а два - go в каждом из массивов '10', так что сумма каждого массива равна 20, а общее число items это девять.

Я не могу добавить дробное число элементов в массив, и числа вряд ли когда-либо будут делиться идеально, как в этом примере, но всегда существует решение, в котором разница между суммами минимальна .

В настоящее время я использую грубую силу для решения этой проблемы, но производительность страдает с большим количеством элементов. Я чувствую, что есть математический ответ на эту проблему, но я даже не знаю, с чего начать.

Answer 1

Легко написать жадный алгоритм, который предлагает приблизительное решение. Просто всегда добавляйте следующий элемент в массив с наименьшей суммой значений.

Массив с наибольшим значением должен быть в пределах 1 элемента правильности.

Для каждого количества элементов в массив с наибольшим значением, вы можете повторить упражнение. Получение массива со вторым по величине значением с точностью до 1.

Продолжите через все из них, и с 6 массивами вы получите 3^5 = 243 возможных расположений элементов (обратите внимание, что количество элементов в последний массив целиком определяется первыми 5). Выберите лучшее из них, и ваш комбинаторный взрыв будет сохранен.

(Этот подход должен работать, если вы пытаетесь минимизировать разницу значений между самым большим и самым маленьким массивом и иметь фиксированное количество массивов.)