Задача

Есть следующая задача (я не знаю, как называется тип этих задач). Имеется n наборов чисел, необходимо перераспределить числа в этих наборах так, чтобы сумма чисел в каждом наборе была равна или примерна равна.

Пример. Есть три набора:
3, 5, 1;
10, 1, 4;
12, 3, 2, 1.
Общая сумма всех чисел равна 42, соответственно в каждом наборе должно быть 42/3=14.
Одно из решений следующее: из третьей в первую переносим числа 3 и 2, из второй в третью переносим число 1.
Получаем
3, 5, 1, 3, 2
10, 4
12, 1, 1

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

Замешай все числа в кучу, после чего решай стандартную задачу распределения грузов по вагонам (ну или задача о ранце).

Спасибо.

Классические задачи этого типа имеют два параметра типа "вес" и "ценность", здесь только один....
Какие существуют алгоритмы для данной задачи?

http://kladovka.net.ru/delphibase/?action=viewfunc&topic=mathalg&id=10413

Цитата Igrek @ 01.09.11, 13:56

Классические задачи этого типа имеют два параметра типа "вес" и "ценность", здесь только один....

вес = const

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

Один рюкзак здесь не подойдёт, тут 3 рюкзака. И вообще здесь ближе не рюкзак,
3-РАЗБИЕНИЕ, NP-трудная в сильном смысле, т.е. за псевдополиномиальное время ДП её не решить. А рюкзак ДП решается куда как хорошо.
Алгоритм который Mbo привёл - метод ветвей и границ, что для NP-трудной в сильном смысле естесственно.
А рюкзачок - задача динамического программирования.

Не могу понять, есть ли полиномиальная сводимость 3-Разбиения к данной задаче.

3-РАЗБИЕНИЕ.
Условие. Заданы множество A, состоящее из 3m элементов, целое положительное число B. Элементы имеют целые положительные размеры такие, что
1. B/4 < s(a) < B/2
2. Сумма размеров всех элементов равна mB.
Вопрос. Можно ли множество A разбить на m непересекающихся подмножеств так, что сумма элементов каждого i-го подмножества равна В? (и каждое подмножество содержит ровно 3 элемента).
Похоже ограничения на размеры и количества даны так, чтобы исключить тривиальные случаи.

Вообще, одно дело точно набирать сумму, другое дело - примерно. Примерно это как? Минимизируем среднеквадратичное отклонение по всем кучкам? Или максимальное отклонение должно быть минимально?

Добавлено 01.09.11, 17:51
Igrek, это учебная задача или производственная?
Для небольшой размерности она решается переборными алгоритмами, например, как предложил MBo.

Сообщение отредактировано: Swetlana - 01.09.11, 17:52

Swetlana, это производственная задача, область электрика. Необходим алгоритм для балансировки фаз. Есть три фазы и n автоматов, необходимо их раскидать по фазам, чтоб сила тока автоматом была более менее сбалансирована.
Важна производительность, а не оптимальность решения, достаточно решения удовлетворяющего условиям.

Сейчас пробую реализовать жадный алгоритм (когда "рюкзаки" по очереди забиваем максимальными возможными элементами).

Пример.

25 15 13 10 8 7 5 3 1 1 1 (уже отсортирован)

ограничение будет, если округлить до минимальной погрешности <=30

Решение.
Первый 25 + 3 + 1 + 1 = 30 (на каждом шаге берем максимально допустимы элемент)
Второй 15 + 13 + 1 = 29
Третий 10 + 8 + 7 + 5 = 30

Алгоритм очень не оптимальный в некоторых случаях...

Цитата Igrek @ 02.09.11, 06:21

Сейчас пробую реализовать жадный алгоритм (когда "рюкзаки" по очереди забиваем максимальными возможными элементами).

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

Akina, попробую. По сути, так и действует человек...

Цитата Igrek @ 02.09.11, 08:06

По сути, так и действует человек...

Нет, как раз чел дейтсвует так, как ты пробовал - наполняет рюкзаки по одному.

Igrek, так бы сразу и сказали, что задача производственная, а вы - не студент-двоешник.
Если размерность маленькая, n<= 25, можно решить перебором, методом ветвей и границ.

Для большой размерности такие задачи очень хорошо решаются локальным поиском. Я решала неоднократно.
Разобранный пример с программой на паскале можно найти здесь, работы равномерно по бригадам распределяются.
http://www.mesforum.ru/viewtopic.php?f=6&t=1569

Сообщение отредактировано: Swetlana - 02.09.11, 11:38

Swetlana, спасибо, почитаю....