|
|
Регистрация Восстановить пароль |
Повторная активизация e-mail |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
|
Опции темы | Поиск в этой теме |
04.02.2009, 09:54 | #1 | |
Программер
Пользователь Подтвердите свой е-майл
Регистрация: 03.07.2008
Сообщений: 36
|
Алгоритм линейного раскроя (финальный рывок)
В общем решил написать алгоритм линейного раскроя методом полного перебора.
Дано: N деталей разной длины и неограниченное количество заготовок длиной L Любая из деталей меньше L Требуется: Разместить все детали на заготовки, используя как можно меньше заготовок и при этом остаток от последней заготовки должен быть как можно бОльшим. Сделал алгоритм составляющий все возможные комбинации деталей, длиной меньше или равно L (длина заготовки). При чём в каждой комбинации любая из деталей используется только один раз (по условию) В аттаче скрин - результат работы алгоритма при 10 деталях разной длины и заготовках длиной 1000. Первые 10 полос - это сами детали (по сути тоже комбинации из одной детали) остальное - их комбинации. ------------------------------------------------------------------------ Теперь то, что я не могу осилить... мозг устал наверное Надо из этих комбинаций выбрать те которые отвечают условию: Цитата:
<AXS> Если один из двух выходов - ловушка, надо найти третий... </AXS>
<AXS> "Живой" - явление временное... </AXS> <><><> www.mak-ms.com <><><> |
|
04.02.2009, 12:28 | #2 |
Программер
Пользователь Подтвердите свой е-майл
Регистрация: 03.07.2008
Сообщений: 36
|
Мне бы только принцип понять. С какой стороны начать... У кого какие мысли есть - выскажитесь.
<AXS> Если один из двух выходов - ловушка, надо найти третий... </AXS>
<AXS> "Живой" - явление временное... </AXS> <><><> www.mak-ms.com <><><> |
04.02.2009, 14:17 | #3 |
Форумчанин
Регистрация: 15.02.2008
Сообщений: 621
|
ИМХО решать надо так... пусть имееться массив загатовок Zag, и деталей Det одинаковой длинны.
1:Возьмем максимальный элемент Det и возьмем наименьшую загатовку в которую он влезет. 2:Уменьшим величину той загатовки которую мы взяли в 1 на величину детали которую взяли в 1. 3: удалим из массива эту деталь 4: если длинна массива >0 то идем к пункту 1, если нет то конец. Только вот не уверен ^_^
Помог? Ну так нажми на весы!
|
04.02.2009, 17:46 | #4 | |
Программер
Пользователь Подтвердите свой е-майл
Регистрация: 03.07.2008
Сообщений: 36
|
Цитата:
А у меня уже варианты наполнения заготовок готовы. Надо только выбрать какие из них составят самый выгодный набор. Кстати одна из коммерческих программ раскроя сделала вот такой крой:
<AXS> Если один из двух выходов - ловушка, надо найти третий... </AXS>
<AXS> "Живой" - явление временное... </AXS> <><><> www.mak-ms.com <><><> |
|
04.02.2009, 18:24 | #5 | |
Форумчанин
Регистрация: 15.02.2008
Сообщений: 621
|
Цитата:
Помог? Ну так нажми на весы!
|
|
04.02.2009, 18:57 | #6 |
Программер
Пользователь Подтвердите свой е-майл
Регистрация: 03.07.2008
Сообщений: 36
|
Как так какой значимее??? Сначала по первому, потом по второму. То есть минимум заготовок на сколько можно разместить все детали = 6. Но вариантов раскроев на 6 заготовок несколько. Вот теперь по второму критерию.
К примеру моя программа раскроя написанная двумя годами ранее сделала крой тоже на шесть заготовок но остаток от последней заготовки на 50 больше чем сделала программа выше ^ Значит этот крой лучше. Сравни:
<AXS> Если один из двух выходов - ловушка, надо найти третий... </AXS>
<AXS> "Живой" - явление временное... </AXS> <><><> www.mak-ms.com <><><> |
04.02.2009, 21:41 | #7 |
Форумчанин
Регистрация: 15.02.2008
Сообщений: 621
|
а в чем собстсвено проблема если перебрали все возможные варианты?
Помог? Ну так нажми на весы!
|
04.02.2009, 23:00 | #8 |
Программер
Пользователь Подтвердите свой е-майл
Регистрация: 03.07.2008
Сообщений: 36
|
Посмотри внимательно первый пост и скрин к нему...
Выбраны все варианты наполнения одной заготовки деталями. А все детали занимают больше чем одну заготовку. Блин, как ещё объяснить? Кто нибудь объясните ему в чём фишка!..
<AXS> Если один из двух выходов - ловушка, надо найти третий... </AXS>
<AXS> "Живой" - явление временное... </AXS> <><><> www.mak-ms.com <><><> |
04.02.2009, 23:46 | #9 |
Форумчанин
Регистрация: 15.02.2008
Сообщений: 621
|
Так а почему же вы не делаете алгоритмом который я тебе предложил? или он не всегда выгоден?
Помог? Ну так нажми на весы!
|
05.02.2009, 01:26 | #10 |
Форумчанин
Регистрация: 15.02.2008
Сообщений: 621
|
Только что надумал... (будем идти перебором)
Пусть M массив состоящий их всех возможных расположений деталей на загатовке. Пусть N массив уже использумемых в раскройке деталей по заготовкам (пока он пуст). Count количестве детай. 1: выберим i-ый элемент массива M такой что его элементы не отмечены N и отметим их в N 2: покуда количество элеменов N не равно Count повторяем 1. 3: обнуляем N.... .... Вот только тоже у самого голова не варит =\ на мысль только одна рекурсия приходит, чтоб его пустить на складывание разных комбинаций =\
Помог? Ну так нажми на весы!
|
|
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
Сортировка линейного массива. C++ DOS | Xeon332 | Общие вопросы C/C++ | 2 | 15.12.2008 16:21 |
Сортировка линейного списка. | ТИВ | Паскаль, Turbo Pascal, PascalABC.NET | 3 | 23.11.2008 22:39 |
Алгоритмы линейного и бинарного поиска. | Seafulf | Паскаль, Turbo Pascal, PascalABC.NET | 4 | 01.03.2008 21:39 |
[За деньги] Написать программу оптимального раскроя заготовок на фрагменты. | Eretik | Фриланс | 3 | 18.12.2007 08:11 |