Задача об укладке грузиков в мешки

k1a2r3t4a

Имеется несколько грузиков с весами (веса для некоторых грузиков могут совпадать) и два мешка. Ставится задача : придумать алгоритм укладки грузиков в два мешка таким образом, чтобы вес наитяжелейшего из мешков был как можно более легким. Другими словами, нужно как можно более равномерно по весу распределить грузики по мешкам.
.Алгоритм для двух мешков
1. считаем сумму всех грузов. Делим величину на два- это будет идеальный вес мешка.
2. Далее все грузики кладем в один мешок Считаем вес мешка.
3. Разница между весом мешка и идельным весом мешка. Находи груз, вес которого наиболее близок к этой разнице. Перекладываем во второй
4. повторяем итерацию до тех пор, пока разница между весом мешка и идельаным весом уменьшается
 Пример:
Грузики : 1,2,2,3,5
5+3+2+2+1 : 0, макс 13, идеал 6.5, разница 6.5, близкий 5
3+2+2+1 : 5, макс 8, идеал 6.5, разница 1.5, близкий 2
3+2+1 : 5+2, макс 7, идеал 6.5, разница 0.5,
Общая задача
N различных грузиков расфасовать по K мешкам, так чтобы вес наиболее тяжелого мешка был как можно легче.
Для общего случая будет так: есть К мешков. Сперва кладем все грузики в один мешок. Вес мешка знаем, идеальный вес мешка знаем. Отсортируем в 1 мешке по весу грузики. Находим в нем самый тяжелый грузик среди тех, которые меньше идеального веса мешка. (то есть близжайший снизу). Затем снова смотрим, но уже для третьего мешка. И т.д. по всем K-1 мешков. Процедуру повторяем, (теперь сравниваем груики из 1 мешка и разницу между текущим весом i-ого мешка и идельаного)...
Пример:
с тремя мешками.
1,2,2,3,5 | 0 | 0 вес 1 мешка - 13. Идеальный 13/3 = 4 1/3. Вес второго мешка 0. Разница : 4 1/3 Ищем для второго мешка - и кладем туда 3
1,2,2,5 | 3 | 0 вес третьего мешка 0. Разница 4 1/3. Ищем для третьего мешка - и кладем туда 2.
1,2,5 | 3 | 2 ищем для второго мешка. Разница 1 1/3. Кладем 1.
2,5 | 1, 3 | 2 ищем для третьего мешк. Разница 2 1/3. Кладем 2.
5 | 1,3|2,2 все. разницу в 1/3 нечем забить
UPDATE : увы, не оптимально.
Пример:
2,3,4,7,8,9,13,14,15
Идеальная укладка в три мешка:
15,7,3 | 2,9,14 | 4,8, 13
Везде вес мешка равен идеальному = 25.
Алгоритм же дает (если модифицировать его так: высыпать грузики на стол, затем расфасовать слева направо по мешкам, дойдя до крайнего мешка расфасовывать справа налево и т.д.)
13,9,2 | 14,8,3 | 15,7,4
т.е. веса 24,25,26 соответственно.
Помогите плиз, може кто знает удобоваримый алгоритм? А то метод перебора имеет сложность N! а таких грузиков сотни, если не тысячи. Поэтому нужен гораздо более быстрый алгоритм.
З.Ы. Есть статья о задаче о ранце в вики: задача о ранце
но это не совсем то, так как там вместимость ранца фиксированная, а здесь мы именно варьируем
вместимость мешков

antcatt77

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

igor196505

Задач о рюкзаке много...
http://neerc.ifmo.ru/wiki/index.php?title=%D0%97%D0%B0%D0%B4...
Мне кажется, ближе всего к твоему случай "Задача о суммах подмножеств" (Value Independent Knapsack Problem если пытаться искать подмноджество с весом элементов, равным оптимальному. Для двух мешков он должен находить оптимальное подмножество (если оно существует при этом дополнение автоматически будет оптимальным. Возможно для общего случая нужно будет придумывать свою реализацию метода "ветвей и границ" или что-нибудь подобное.

LipkinKS

http://en.wikipedia.org/wiki/Partition_problem
There is an optimization version of the partition problem, which is to partition the multiset S into two subsets S1, S2 such that the difference between the sum of elements in S1 and the sum of elements in S2 is minimized. The optimization version is NP-hard.

Nonnik

Для двух мешков "псевдополиномиальный" алгоритм вроде такой: пусть грузики весят w_1,...,w_N и всего W. Пусть D[i][j] наименьшая разница с весом i которую можно получить из j первых грузиков, тогда ответ в D[W/2][n] и
D[i][j] = min(D[i][j-1], D[i-w_j][j-1])
D[0][1..n] = 0, D[1..W/2][0] = 1..W/2, все другие начальные значения: плюс бесконечность.
Рекурсивная формула читается так: решение либо не содержит груз x_j (D[i][j-1]) либо содержит его.(Скопировал решение из partition problem с предыдущей ссылки :) )
Для К>=3 не вижу будет это работать или нет
Оставить комментарий
Имя или ник:
Комментарий: