5

Есть у нас набор сообщений (80 штук) длиной от 3 до 70 символов. Есть определенные контейнеры, в которые может входить произвольное кол-во сообщений, но их суммарная максимальная длина ограничена 100 символами. Помогите найти оптимальный (с точки зрения быстродействия в том числе) алгоритм, при котором все сообщения могут быть размещены в минимальном числе контейнеров.

3 ответа 3

2

Метод упаковки рюкзака.

5
  • Сто пудов учебная задача. И еще смотри, чего хотят от бедного студента: > Помогите найти оптимальный (с точки зрения быстродействия в том числе) алгоритм Оптимальный алгоритм для NP задачи им подавай. Хоть гипотезу Римана доказать не просят, и то сахар.
    – Ali
    19 сен 2011 в 9:53
  • Да нет, здесь же не один рюкзак. Больше подходит задача об упаковке в контейнеры оттуда же, но у меня простой одномерный случай а такие алгоритмы там не рассмотрены.
    – pacxa
    19 сен 2011 в 9:53
  • Ну, вы можете упаковать один рюкзак, потом второй. И так далее, пока фразы не закончатся. Вам доказать, что это будет оптимальная упаковка с точки зрения числа контейнеров? Насчет производительности... @alienator прав, ой прав. =) Но думаю, мой вариант прокатит.
    – knes
    19 сен 2011 в 10:02
  • Не, отдельные рюкзаки ты упаковывать не предлагай. Когда контейнеров несколько, задача немножко другая. Алгоритмы (best fit, first fit) легко нагугливаются.
    – Ali
    19 сен 2011 в 10:04
  • 1
    Нет, задача не учебная, в том-то и дело. Задача вполне реальна и очень важна экономически. Я ее несколько абстрагировал конечно. Но нагрузка предполагается колоссальная, поэтому так важна оптимизация произоводительности и минимизация числа контейнеров. Ладно, попробую нагуглить ваши алгоритмы best fit, first fit.
    – pacxa
    19 сен 2011 в 10:57
1

В чистом виде задача об упаковке (англ. Bin Packing Problem). Отличается от задачи о рюкзаке на словах совсем немного, но с точки зрения решения - очень сильно.

Эта задача является NP-трудной - то есть полиномиальное решение не найдено. Динамическим программированием эта задача также не решается - так что искать решение следует или перебором - или же можно плюнуть на оптимальность решения и искать субоптимальное эвристиками.

Теперь по поводу этих самых эвристических алгоритмов. Переписываю с Википедии, чтобы не надо было искать.

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

Алгоритм First Fit Decreasing (FFD) при этом помещает очередное сообщение в первый попавшийся контейнер, алгоритм же Best Fit Decreasing (BFD) помещает сообщение в тот контейнер, где после этого останется меньше всего свободного места.

-2

В принципе, данный алгоритм не будет особо сложным. Из всего берется наибольшее число, вычитается из максимума, чтобы понять сколько нам осталось, ищется максимальное число, которое меньше или равно остатку, кладется в контейнер. Опять смотрим сколько еще осталось и снова производим поиск чтобы "забить до потолка". И так с каждым числом. Муторно, но работать должно. Сейчас вот сижу делаю скрипт на пхп чтобы проверить).

4
  • 2
    Контейнер вмещает 10. Есть числа: 6, 3, 2, 2, 2, 5 По вашему алгоритму будет: 6+3 = 9 5+2+2 = 9 2 = 2 Три контейнера, хотя можно запихать в два: 6+2+2, 5+3+2
    – knes
    19 сен 2011 в 11:40
  • Значит, начинаем с середины, и идем переборкой вверх.
    – Grimon
    19 сен 2011 в 12:18
  • По идее, вообще, еще и проверки, например, берем 6+3, если нет дополнения до максимума, то смотрим 6+2. Если тут максимум набирается, то оставляем так. И так по всем проходить. Но алгоритм будет достаточно долгим.
    – Grimon
    19 сен 2011 в 12:40
  • 1
    Любой алгоритм будет неоптимальным в общем случае. Но может быть максимально приближен к оптимальному при соответствующем усложнении. А те алгоритмы, которые мне посоветовали выше (best fit, first fit) простые, и там есть ограничение сверху по их неоптимальности - википедия пишет что Стратегии Best Fit Decreasing и First Fit Decreasing используют не более (11/9)*N + 1 контейнеров (где N - число контейнеров при наилучшем решении задачи). Вроде как есть более оптимальные решения, но они сложнее так что видимо ограничусь такой точностью.
    – pacxa
    19 сен 2011 в 12:46

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.