Как разместить N файлов по папкам?

Question

[ddd329]

Каким алгоритмом можно решить следующую задачу: дано N файлов, каждый из которых имеет свой размер. Необходимо разместить файлы в папках так, чтобы размер файлов в каждой папке не превышал 2 мегабайта, и чтобы количество папок было как можно меньше?

Comments

[VoidVolker]

ddd329 Правила 5.12

[ddd329]

Я понял, но это не конкретная задача, а более абстрактная, что-то типа задача о рюкзаке.

[Lynn «Кофеман»]

Ну собственно это и есть вариация задачи о рюкзаке

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

[#]

ddd329, Lynn «Кофеман», именно она (ну или вариация)

[Wataru]

Lynn «Кофеман», задача об упаковке

[Lynn «Кофеман»]

#, Wataru, ну да

[ddd329]

Wataru, в принципе то, что я и хотел услышать - это задача об упаковке. Мне нужна была большое классификация, а не прямо конкретное решение. Спасибо!

[#]

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

[#]

Wataru, если еще точнее - Мультипликативный рюкзак

[ddd329]

#,

Мультипликативный рюкзак (англ. Multiple Knapsack Problem) — есть N предметов и M рюкзаков (M⩽N).

Здесь M фиксированное, как я понял из формулировки, а у меня M динамическое.

[#]

ddd329, не

(M⩽N)

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

[ddd329]

#, домашняя комбинаторика

[#]

ddd329, или не оптимальный результат, или не предсказуемое время выполнения...
хотя по формулировке, вряд ли вам критично важен идеальный результат ))

[Wataru]

#, Принципиальная разница с рюкзаком в целевой функции. В задаче о рюкзаках надо максимизировать сумму весов объектов, в задаче об упаковке - количество рюкзаков.

[ddd329]

#,

вряд ли вам критично важен идеальный результат

Да, идеальный не нужен. Не нужен очень плохой))

[#]

Wataru, а размер файлов, и их сумма - не эквивалент веса? )) .. и вроде цель тс, как раз минимизировать количество рюкзаков )))...
... мог что то и упустить ))

[Wataru]

#, Ну вот, в мульти-рюкзаке надо максимизировать общий размер файлов. Но в этой задаче он всегда один фиксированный - надо распихать по папкам все файлы. Зато в этой задаче надо минимизировать не фиксированное количество папок. А в мультирюкзаке это количество обязательно фиксировано.

[Михаил Лялин]

в реальности - архивация по размеру архива с помещением каждой части архива в свой каталог ;-)

[#]

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

Answer 1

[Wataru]

Это задача об упаковке. Она сложная. И ближе даже не к задаче о рюкзаке, а к задаче о мульти-рюкзаке. Для больших размеров файлов и N решения, кроме переборного, нет.

Если N маленькое, то есть быстрые алгоритмы вроде Динамического Программирования. Но там и перебор будет не то, чтобы сильно медленнее.

Если вам не важно получить абсолютно минимально возможное количество папок, то подойдет какое-нибудь жадное решение. Оно даст хорошее приближение. Скажем, вместо 30 идеальных папок вы часто получите 40.

Например, кладите файлы в текущую папку, пока они туда помещаются. Потом создавайте следующую папку. Заполняйте ее, пока размер папки + размер следующего файла <= 2Mb.

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

Answer 2

[Сергей Соловьев]

1. Сортируешь все файлы по размеру
2. Берешь самый большой файл и помещаешь в первую папку
3. Дальше каждый файл по убыванию размера:
1. Находишь папку с наименьшим оставшимся размером, который позволяет добавить туда файл
2. Если таких нет - создаешь новую папку и кладешь туда

Comments

[ddd329]

Хорошо.
А такой вариант?
1. Сортируем файлы по размеру от самого большого, до самого маленького, т.е. по убыванию;
2. Берем первый (самый большой) файл и помещаем его в первую папку;
3. Далее начиная со второго файла перебираем все подряд и пробуем разместить его в 1-ой папке, если не получается, то тогда создаем новую, ну и т.д.

[Сергей Соловьев]

ddd329, можно

[#]

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

[Сергей Соловьев]

#, как раз таки потому что это задача о рюкзаке предложил более менее практическое решение (на мой взгляд)

[#]

Сергей Соловьев, все равно комбинаторику не обойти

[Сергей Соколов]

Ну и зря отмечено решением. Потому, что «задача о рюкзаке» в общем случае решается только полным перебором всех вариантов.

[ddd329]

Сергей Соколов, вполне себе хороший ответ, мне нравиться. Более-менее, что-то конкретное написано. Да, может он и не даст самый оптимальный вариант, но "самый" и не нужен.

Answer 3

[#]

вам сюда

ps ок. на математику не учились. бывает. остается выбор декларативного (или функционального языка)... (мой любимый шарп уже практически оброс функциональщиной...)...
... и тупой перебор вариантов... а он может оказаться долгим... но это правда жизни