Cyberholic,

Сколько в вашем бизнесе объектов типа "автор", "книга", "полка", "ряд"?
Сколько времени вы можете дать компьютеру на нахождение оптимального решения?

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

Cyberholic,

Ясно. Похоже, что простым перебором решать не стоит.

На мой взгляд, требуется уточнить критерий оптимальности, что значит "максимум свободного места"? Очевидно, что сумма свободного места остается неизменной, меняется только распределение этого свободного места по непрерывным свободным участкам в пределах ряда. Вы должны сформулировать функцию, которая, имея на входе набор свободных участков, выдает некоторое число, выражающее качество данного набора. Например, эта функция должна четко различать, что лучше: два свободных участка шириной 4 каждый, или один шириной 5 и второй шириной 3. Или еще лучше один шириной 6 и два шириной 1 каждый?

Далее, в эту функцию необходимо вплести количество перестановок. То есть, если распределение 5+3 из примера выше лучше чем распределение 4+4, но для него потребуется N дополнительных перестановок, то при каких N считать его по-прежнему лучшим?

И напоследок, необходимо в эту функцию вплести метрику того, как численно выразить книги одного автора, стоящие рядом или не рядом. То есть, если в нашем же примере при решении 5+3 книги идут вразнобой, а при решении 4+4 - авторы максимально сгруппированы, то какое решение лучше и насколько? Или сколько дополнительных перестановок можно делать для цели групировки книг одного автора вместе?


Если эту функцию удастся четко сформулировать и перевести всю задачу на формальный язык для систем планирования, то можно для поиска решения применить какой-нибудь высокооптимизированный планировщик (например, FF planner http://www.loria.fr/~hoffmanj/ff.html).

Cyberholic,

теперь все четко ;)
Можете использовать решение, предоставленное автором refreg.
Я бы добавил после п.2 такое

3. Создаем пустой список решений.
4. Сотрируем расстояния от перегородки до перегородки по убыванию (романы теперь стали перегородками).
5. Берем первое такое расстояние.
6. Пытаемся все книги из этого участка переложить на свободные места на других полках.
7. Если смогли все переложить, то ответ готов. Касательно картинок min-1, min-2 и т.п. - они формируются тут же.
8. Если не смоги все переложить, и что-то осталось, то это что-то сдвигаем вплотную к стенкам.
9. Если освобожденное пространство больше, чем следующее в списке из п.4, то ответ готов.
10. Если меньше, то добавляем наше решение в список возможных решений.
11. Если в сортированном списке расстояний из п.4 есть следующий кандидат, берем его и переходим к п.6.
12. Если следующего варианта нет, то ищем с списке решений решение с максимальным итоговым свободным расстоянием. Это и есть ответ.

CyberholicNo ved Punkti 1 i 2 predidushego resheniya predpolagayut perestanovku iz ryada v ryad, chto nevozmozhno po usloviyam...

На мой взгляд, не предполагают:
refreg1. Т.к. из ряда в ряд нельзя перекидывать , убираем все ряды оставляем один (для других рядов задача аналогична)
2. Т.к. романы нельзя передвигать - превращаем их в перегородки


Ваш интерес в решении задачи непонятен: он есть или его нет?

CyberholicChto oznachaet "Uchastok".
Rasstoyanie ot peregorodki do peregorodki est pustoe mesto, iz "uchastka" s samim bolshim pustim mestom perekladivaem knigi na svobodnie mesta na drugih polkah. Chto oznachaet uchastokn i kak ego mozhno "opredelit" v dannom kontekste?

Вы из-за границы пишете? Попробуйте сайтик типа http://translit.ru/.
Участок - это область полки, заключенныя между неперемещаемыми границами. Неперемещаемые границы - это перегородки и романы.

Участок может быть как пустой, так и с книгами.