Проблема упаковки - PullRequest
Новая
       4

Проблема упаковки

4 голосов
/ 12 ноября 2010

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

У меня есть набор папок, которые мне нужно записать на компакт-диски. Папки не могут быть разделены: каждая папка идет на один диск.

Я хочу заполнить диски наиболее эффективно:

  1. Минимизируйте количество дисков и
  2. Количество дисков, равных, максимально увеличить доступное пространство для наименее заполненного диска (80 + 20 оставшееся пространство лучше, чем 50 + 50).

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

Ответы [ 2 ]

4 голосов
/ 12 ноября 2010

Это называется Проблема упаковки в бункер и является NP-трудной, поэтому не существует простого алгоритма для ее решения.

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

Это быстро решает проблему, так как после сортировки остальная часть алгоритма - O (n).

В конкурсе, в котором я участвовал, это привело к 74 дискам вместо 79, которые наивное решение могло бы достичь для нашего самого большого набора тестовых данных.

2 голосов
/ 24 августа 2011

Если вы хотите упаковать файлы / папки на один диск CD-R , то вы можете сделать это оптимально за псевдополиномиальное время.Для этого вам необходимо округлить размеры файлов / папок по секторам и сосчитать сектора, доступные на CD-R.

После этого мы получим проблему упаковки дискретных 1-D ранцев , которая может быть легко решена с помощью динамического программирования, со сложностью O (n) ,

Более конкретно:

  • O (n) = O (nW) , причина W в вашем случае постоянна - W - количество секторов на CD-R.
  • n количество файлов / папок.

Для повышения производительности вы всегда можете чрезмерно приблизить размер секторов, пример настройки:

  • с чрезмерным приближениемразмер сектора 70k
  • , что составляет 700M / 70k = 10k всех секторов на CD-R
  • , которые должны вычисляться в секундах, когда количество файлов меньше (1G / 10k = 100k) 100k - n <100'000 </li>
  • в минутах, когда n <10'000'000 </li>

Более того:

  • решение может быть приятно параллельно.

Может быть, применение этого алгоритма жадным образом «упаковать один компакт-диск, упаковать следующий компакт-диск» будет работать?

...