Форум программистов, компьютерный форум, киберфорум
Наши страницы
Алгоритмы
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.60/5: Рейтинг темы: голосов - 5, средняя оценка - 4.60
ЕвгенийАндреич
0 / 0 / 0
Регистрация: 12.07.2018
Сообщений: 47
1

Оптимальный распил палок

16.01.2019, 17:35. Просмотров 863. Ответов 12
Метки нет (Все метки)

Д.в.
Нужен алгоритм для решения следующей задачи или если он есть, то как называется?
Есть доски длинной 2000 мм. Есть список с досками от 300 мм до 1000 мм. Мне нужно написать программу (не важно на каком языке, мне главное алгоритм), которая считает сколько надо досок, чтобы напилить палки из списка с минимальным остатком, что бы сложить все остатки в одну сумму и получилось как можно меньше. ну и соответственно чтобы знать сколько палок надо распилить на какие размеры. Например 10 досок пилим на три палки - 600, 500 и 300, 4 доски пилим на 800 и 900, и т.д.
Что можете предложить? Всю голову сломал. Есть алгоритм "Упаковки рюкзака", но там учитывается "цена" и "Вес", а мне как бы надо просто "вес". заранее спасибо тому кто что то подскажет)

Добавлено через 16 минут
Как думаете? Если взять палку 2000, и методом перебора (благо список не очень большой) подставлять все комбинации с размерами из списка, выбрать оптимальную комбинацию, из списка вычесть палки которые в этой комбинации и прибавить к нужному количеству досок +1 . И так делать до тех пор, пока в списке с палками не останется ничего???
Это будет оптимальный вариант?
0
Лучшие ответы (1)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
16.01.2019, 17:35
Ответы с готовыми решениями:

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

Оптимальный алгоритм сортировки
Камрады! Есть функция/процедура f(m,n), которая получает 2 номера и возвращает n,m (n>m) т.е....

Оптимальный план перевозок
Задана карта, на которой показана транспортная сеть, точки расположения складов с товаром и гаражи...

Оптимальный поиск элемента в массиве
Столкнулся с проблемой поиска оптимального алгоритма нахождения индекса нужного мне элемента в...

Оптимальный язык Web-программирования
Профессионалы в Web-программировании, Выскажите свое мнение по поводу выбора языка...

12
Fulcrum_013
1541 / 1187 / 138
Регистрация: 14.12.2014
Сообщений: 10,106
Завершенные тесты: 3
16.01.2019, 17:58 2
Лучший ответ Сообщение было отмечено ЕвгенийАндреич как решение

Решение

Цитата Сообщение от ЕвгенийАндреич Посмотреть сообщение
Есть алгоритм "Упаковки рюкзака", но там учитывается "цена" и "Вес", а мне как бы надо просто "вес"
Только рюкзаков получается много а не один.
палки сортируются по убыванию остатки по возрастанию. Ну и дальше впихивается что куда впихнется. Т.е. наибольшая палка сравнивается с досками начиная с наименьшего остатка, когда найдена остаток оставшийся после ее обрезки вставляется в массив остатков с сохранением упорядоченности. По сути получается выбор минимального остатка куда влезет очередная палка. "т.е. первый подходящий с упорядочиванием" Основной из пользуемых в промышленности методов в силу своей простоты и достаточно высокой эффективности.
Ну в общем то есть попытки его апгрейда которые в худшем случае работают не хуже. к примеру вот тут
1
Excalibur921
764 / 460 / 80
Регистрация: 12.10.2013
Сообщений: 3,085
16.01.2019, 23:14 3
Лучше брутофорса ничто не решит. Другое дело хватит ли мощности =).
0
ЕвгенийАндреич
0 / 0 / 0
Регистрация: 12.07.2018
Сообщений: 47
17.01.2019, 08:07  [ТС] 4
Цитата Сообщение от Fulcrum_013 Посмотреть сообщение
Только рюкзаков получается много а не один.
палки сортируются по убыванию остатки по возрастанию. Ну и дальше впихивается что куда впихнется. Т.е. наибольшая палка сравнивается с досками начиная с наименьшего остатка, когда найдена остаток оставшийся после ее обрезки вставляется в массив остатков с сохранением упорядоченности. По сути получается выбор минимального остатка куда влезет очередная палка. "т.е. первый подходящий с упорядочиванием" Основной из пользуемых в промышленности методов в силу своей простоты и достаточно высокой эффективности.
Это для вычисления необходимого количества досок. А как то можно сделать , чтобы получить "карту раскроя" - т.е. на какие размеры сколько пилить досок?
0
Fulcrum_013
1541 / 1187 / 138
Регистрация: 14.12.2014
Сообщений: 10,106
Завершенные тесты: 3
17.01.2019, 09:28 5
ЕвгенийАндреич, Ну вот именно карту раскроя так и определяют. При этом для ускорения вместо массива палок можно использовать кучу. Именно поэтому динамическую память и называют еще кучей - для ее "раскроя" тот же алгоритм оптимизации применяется. При этом на практике есть еще такое понятие как нижний предел размера остатка пригодный для дальнейшего использования. С учетом этого факта даже полный перебор если и дает выигрыш то редко и очень незначительный.
0
vantfiles
138 / 69 / 26
Регистрация: 07.05.2013
Сообщений: 244
17.01.2019, 15:33 6
Вот тут было похожее обсуждение:

Задача на минимизацию остатков
0
Excalibur921
764 / 460 / 80
Регистрация: 12.10.2013
Сообщений: 3,085
17.01.2019, 15:50 7
Представьте цех 100 000 тон дерева в год и немного неоптимальный раскрой...

Лучше результата чем от брутофорс не существует с природе, его результат это эталон для всех других решений. Другое дело, что не всегда есть вычислительная мощность для него. Поэтому придумывают всякие уловки\усложнения\альтернативы.

Цитата Сообщение от ЕвгенийАндреич Посмотреть сообщение
и методом перебора (благо список не очень большой)
Смогли бы посчитать брутофорсом за это время пока выясняете тонкости другого подхода?
0
Fulcrum_013
1541 / 1187 / 138
Регистрация: 14.12.2014
Сообщений: 10,106
Завершенные тесты: 3
17.01.2019, 16:45 8
Цитата Сообщение от Excalibur921 Посмотреть сообщение
Лучше результата чем от брутофорс не существует с природе, его результат это эталон для всех других решений. Другое дело, что не всегда есть вычислительная мощность для него. Поэтому придумывают всякие уловки\усложнения\альтернативы.
Был у нас на городской олимпиаде в 90-х эта задача под названием "задача о нескольких рюкзаках" присутсвовала. Пройтить все тесты смогли только эти два метода - полный перебор рекурсией ака "брут" и "первый подходящий с упорядочиванием". Потому как НИИ Искуственного Интеллекта которое оную олимпиаду организовывало запарилось искать набор данных на которых брут превзошел бы. Хотя такие наборы данных действительно существуют.
0
vantfiles
138 / 69 / 26
Регистрация: 07.05.2013
Сообщений: 244
17.01.2019, 18:33 9
Кстати, вопрос - это теоретическая задача или практическая?

На практике оптимизируя один заказ можно получить заметно больше отходов, чем оптимизируя несколько заказов.
Если же заказы поступают раз в сутки, то лучше заложиться не на минимизацию отходов - а на "полезные остатки" - то есть обрезки, которые могут пригодиться в дальнейшем в других заказах.
1
ЕвгенийАндреич
0 / 0 / 0
Регистрация: 12.07.2018
Сообщений: 47
22.01.2019, 11:13  [ТС] 10
Fulcrum_013, спасибо. Работает. Написал программу по твоему алгоритму в VBA Excel, кроит один в один как Базис Мебельщик раскрой. Т.к. у меня все ведется в экселе не хотелось привлекать стороннею программу для раскроя, а так хоп хоп и все работает четко
0
Excalibur921
764 / 460 / 80
Регистрация: 12.10.2013
Сообщений: 3,085
22.01.2019, 17:00 11
ЕвгенийАндреич, Для эксперимента не пробовали сверять с брутофорсом?
Критерии оценки:
1)размер остатков
2)кол-во строк кода.
3) разбор матана\кода метода
0
ЕвгенийАндреич
0 / 0 / 0
Регистрация: 12.07.2018
Сообщений: 47
22.01.2019, 20:17  [ТС] 12
Excalibur921, не пробовал, не когда. Я и так проэкт на долго затормозил. Когда закончу, буду его совершенствовать ,вот и попробую
0
Fulcrum_013
1541 / 1187 / 138
Регистрация: 14.12.2014
Сообщений: 10,106
Завершенные тесты: 3
22.01.2019, 21:16 13
Цитата Сообщение от ЕвгенийАндреич Посмотреть сообщение
кроит один в один как Базис Мебельщик раскрой
Реально это одна из первых лабораторок по курсу САПР в универе. Вернее ее половина. Вторая половина то же самое для 2D случая с прямоугольными листами и заготовками. Так что весь раскрой деланный "на скорую руку" работает именно так.
0
22.01.2019, 21:16
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
22.01.2019, 21:16

Перебор цифр и оптимальный алгоритм
Всем, добрый день. Есть набор цифр от 1 до 5. В числе может быть от 1 до 15 цифр. Например,...

Оптимальный алгоритм распределения образа на N машин
Задача. Надо доставить образ VM на N(20) машин по сети. Хотелось бы придумать оптимальный альгоритм...

Найти методом потенциалов оптимальный путь от пункта 1 к пункту 9
Найти методом потенциалов оптимальный путь от пункта 1 к пункту 9(помогите пожалуйста)!


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
13
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2019, vBulletin Solutions, Inc.
Рейтинг@Mail.ru