Люди, не подскажите хороший алгоритм:
Есть лист металла. Нужно его распилить так, чтобы получить требуемый перечень листов меньшего размера с заранее заданными размерами. При этом следует максимально минимизировать остатки большого листа.

симплекс метод :)

А вообще есть куча программ для раскроя, с учетом отходов на стружку, технологического оборудования и т. д.

(0) задача имеет кучу решений - можно нарезать много листиков но маленьких а можно нарезать много разных - критерий оптимальности есть?

+(3) по крайне мере площадь остатка будет одной и той же

(0) Это называется карта раскроя. Задача достаточно сложная, для быстрого решения в лоб, т. к. зависит от специфики производства, оборудования, который этот распил будет производить, трудозатрат и т. д. Если подходить примитивно, то нужно решить задачу линейного программирования, но тут возникает фокус с формой, если форма хитрая, то простого решения не будет. Для упрощения задачи можно рассматривать прямоугольники, ну и т. д.

если прямоугольниками - то просто

(5, 6) Только прямоугольники

(7) jlbyfrjdst&

(7) одинаковые?

1. ЛП не подходит
2. Непросто и для прямоугольников.
3. Лет 5-6 назад пробовал делать для раскроя на продольно-поперечных станках (раскрой из рулона). Если коротко, то решал методом ветвей и границ и алгоритм был разным для "стандартных" деталей и "произвольных". Для стандартных предварительно делался расчет. По реальным заказам (примерно 100-200) статистика была такой:
- по стандартным отходы около 2%;
- по нестандартным - 12-15%.
Пытался "впарить" в несколько фирм (производство кровельных элементов) - оказалось не нужно: "У нас отходы за счет заказчика". В ассоциации металлоторговцев на предложение организовать семинар отреагировали так же.
Тема интересует, если не найдете готового решения, готов поучаствовать безвозмездно.

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

(11) Как происходит раскрой листа: можно ли резать не насквозь (гильотина, болгарка, газовая резка?).
Году в 83 был на Уралмаше, в цехе раскроя листов стояла японская установка (газовые резаки), операторы на дисплее формировали раскрой (типа тетриса), их за экономию поощряли.

кури:
http://c-a-m.narod.ru/computers/soft-raskroj.html

если так пошло то вот :)
http://forum.sources.ru/index.php?showtopic=240211&hl=

не понял критерий

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

(15, 16) Листов несколько. Цель - минимизировать остатки от "большого" листа. В идеале их не должно быть вообще. Если лист использован не полностью - он может быть использован в последующем раскрое. Последующий раскрой на данный момент не рассматривается...

(9) Нет.

(12) Можно резать не насквозь. Деталей технологии не знаю...

В конце 90-х годов готовые решения для металлистов и мебельщиков лежали как платные программы на (по-моему) download или listsoft. Цена начиналась от 3000 вечнозеленых...

можно что-нибудь из комбинаторики попробовать
1. т.к. фигуры прямоугольные, то каждая деталь может быть
либо | либо -
2. сортирум детали по наибольшему измерению
3. кладем деталь1 к краю листа - в угол
4. ищем свободное место для деталь2
5. располагаем дет2 чтобы прикасалась к уже уложенным деталям
6. идем в 4. пока не кончится место или детали
----
собственно "укладка рюкзака" получилась
фишка:
7. считаем отходы и запоминаем расположение деталей
8. делаем "шаг назад" и переворачиваем | - детали
9. идем в 7. пока не переберем все позиции деталей
проблемы:
4. непросто это будет
5. тоже хитро
ну и количество вариантов ... 1с не самый шустрый язык
---
все имхо, чисто мысли вслух

2. ну и сортировать можно по площади, а не по наибольшему измерению

Программы из списка в (13) не пробовали погонять на Ваших данных?

(23) В свое время тестил BestCute Pro, для составления карт раскроя в мебельном производстве. Сравнительное тестирование производили на плотнике краснодеревщике :). В принципе процент отхода был сопостовим, но по времени работы, краснодеревщик оказался круче. Хотя и программа весьма неплоха была :)

(24) Странно, что краснодеревщик обогонял по времени. Если бы по качеству решения - было бы понятно. Может в программе перебор организован? Не могли бы вспомнить, как долго считала программа и насколько время расчета зависело от параметров задачи (числа деталей).

(25) Не по времени расчета,  по времени (трудозатраты) на распил. :)
Я не закладывал станки, ну и много других параметров. Соответственно зная специфику оборудования, у краснодеревщика получалось лучше. Насколько помню, станки могут быть очень разные и очень много параметров можно учитывать.

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

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

Из достоинств той системы помню вот что:
1) Учет возвратных отходов
2) Учет ширины распила
3) Учет по видам материалов
4) Учет различной технологии распила
5) Учет обработки кромок
6) Учет стоимости материалов по партиям
7) Ну и много чего еще

Система более менее имела дружелюбный интерфейс и мне нравилась, но к сожалению денег на покупку не хватило :(.

По скорости работы к сожалению замеров уже не осталось, но помню покурить успевал :) (вообще-то :( - курить вредно!)

(26) Спасибо.

(27) Михаил, просто ради интереса, Вы занимались калькулированием затрат? Если интересно у меня остался достаточно простой алгоритм калькулирования затрат в производстве с коротким, многоступенчатым технологическим циклом. Была мысль сделать ветку, но пока что думаю, будет ли кому это тут нужно.

Нет, не занимался. И производством, по сути, тоже. Так что от меня здесь, как от козла молока.

(29) Ну тогда ладно :). Удачи!

(28) Делай - интересно.