Почитал топик про хитрую сортировку, мало что понял, но вспомнил одну так и не решённую мной задачу:
Есть большой лист бумаги. есть много мелких листов не одинаковой, но прямоугольной формы.
Задача разложить эти маленькие листки на большом(или нескольких больших) так, чтобы занять как можно меньше больших листов, а свободное от мелких листов пространство было как можно большим(не мелкими кусочками по листу, а одним свободным куском где-то в углу)
Сам я додумался только до последовательного перебора — когда подставляю в верхний левый угол листа один квадратик, к нему справа следущий и так до конца строки, потом снизу новую строку, с проверкой выпирающих в верхней строке.
И дополнительное, не обязательное условие, чтобы можно было полученную раскладку резать по прямым линиям. Например: у нас есть 10 мелких в верхней строке, один крупный в следущей слева и 5 помельче справа. сначала отрезаем мелкие. потом отрезаем крупный от пяти соседних и их уже шинкуем.
В общем вот такой вопрос (такой алгоритм реализуется в мебельных конторах из ДСП детали делают и есть программы, но их алгоритма я не понимаю
).
Это не совсем сортировка. Погугли по словосочетанию "задача оптимального раскроя". Если резать только по прямым линиям — добавить слово "гильотинный".
А вообще задача np-полная, большинство методов решения — оптимизированные (направленные) варианты перебора.
Здравствуйте, dmitryk1, Вы писали:
D>Сам я додумался только до последовательного перебора — когда подставляю в верхний левый угол листа один квадратик, к нему справа следущий и так до конца строки, потом снизу новую строку, с проверкой выпирающих в верхней строке.
Делал примерно так же
http://www.rsdn.ru/Forum/Message.aspx?mid=569482&only=1Автор: FreshMeat
Дата: 16.03.04
Работало на ура.
