 |
| Алгоритм |
| Kazimar | Дата: Вторник, 02.03.2010, 21:38 | Сообщение # 1 |
 Лейтенант
Группа: Пользователи
Сообщений: 67
Репутация: 3
Статус: Offline
| Всем привет!!! Помогите составить оптимальный алгоритм. Задача такова: есть склад на котором есть доски разной длины. Необходимо, учитывая входящие данные для подсчета (длина доски и количество досток этой длины), рассчитать самый оптимальный способ порезки досток. Так чтобы отходы были минимальными. Если у кого-то есть какие-то мысли, буду очень благодарен. Спасибо!!!
|
| |
|
| |
| Zaval | Дата: Вторник, 02.03.2010, 21:52 | Сообщение # 2 |
|
Генерал-полковник
Группа: Пользователи
Сообщений: 1005
Репутация: 130
Статус: Offline
| Ежели на спички - то по 5 см - самое то будет:)
Киев
|
| |
|
| |
| liksoft | Дата: Вторник, 02.03.2010, 22:18 | Сообщение # 3 |
 Полковник
Группа: Пользователи
Сообщений: 203
Репутация: 98
Статус: Offline
| Quote (Zaval) Ежели на спички - то по 5 см - самое то будет
|
| |
|
| |
| Ardi | Дата: Вторник, 02.03.2010, 22:34 | Сообщение # 4 |
 Генерал-лейтенант
Группа: Пользователи
Сообщений: 694
Репутация: 123
Статус: Offline
| Есть специальные разделы математики для таких задач.
Может "эконометрия", может как-то подругому называется. Пусть наймут математика. Тем более что применение этих алгоритмов мгновенно уменьшит затраты предприятия на доски процентов на 30.
Киев .
помог - плюсуйте . icq 562128720
Сообщение отредактировал Ardi - Вторник, 02.03.2010, 22:35 |
| |
|
| |
| Anderson | Дата: Среда, 03.03.2010, 10:28 | Сообщение # 5 |
 Полковник
Группа: Пользователи
Сообщений: 158
Репутация: 19
Статус: Offline
| Сходи в институт в какому-нибудь преподу по вышке и он за 100$ в течение часа выдаст формулу. Если ты из Киева могу дать доктора математических наук у меня читала вышку в институте для ее это как семочки.
|
| |
|
| |
| venger | Дата: Среда, 03.03.2010, 10:31 | Сообщение # 6 |
 Рядовой
Группа: Пользователи
Сообщений: 16
Репутация: 3
Статус: Offline
| (1) Важна только длинна и кол-во досок и длинна и кол-во получаемых кусков? Или еще и ширина, материал (дуб, сосна и т.д.) и т.п.? Опять таки, есть еще такой нюанс, есть ли понятие "ценности" доски по длинне, т.е. когда отходы будут одинаковы, но резать лучше более мелкие доски, а длинные оставлять, при равных расходах или даже ценой небольшого увеличения отходов стараться по максимуму использовать более мелкие доски...
http://venger.narod.ru
Сообщение отредактировал venger - Среда, 03.03.2010, 10:34 |
| |
|
| |
| Kazimar | Дата: Среда, 03.03.2010, 10:52 | Сообщение # 7 |
|
Лейтенант
Группа: Пользователи
Сообщений: 67
Репутация: 3
Статус: Offline
| Venger учитыват толщину, материал или еще что-то кроме длины и количества не нужно
|
| |
|
| |
| Ardi | Дата: Среда, 03.03.2010, 12:59 | Сообщение # 8 |
|
Генерал-лейтенант
Группа: Пользователи
Сообщений: 694
Репутация: 123
Статус: Offline
| А ещё есть варианты когда нужно получить >= 200 досок размера А, >= 300 досок размера Б. И остальное нарезать с минимальными отходами.
Только они не догадались тебе такую постановку ещё сказать.
Киев .
помог - плюсуйте . icq 562128720
|
| |
|
| |
| venger | Дата: Четверг, 04.03.2010, 10:38 | Сообщение # 9 |
|
Рядовой
Группа: Пользователи
Сообщений: 16
Репутация: 3
Статус: Offline
| Это скорее элементы комбинаторики и алгоритм все-таки надо думать (формулу одну тут не применишь).... Т.е. как уложить на полках разной длинны, книги разной толщины, чтобы места на полках осталось по минимуму и как можно меньше полок было занято.... Интересная задача....
http://venger.narod.ru
|
| |
|
| |
| Zaval | Дата: Четверг, 04.03.2010, 13:06 | Сообщение # 10 |
|
Генерал-полковник
Группа: Пользователи
Сообщений: 1005
Репутация: 130
Статус: Offline
| Kazimar, если хотите получить что-либо посущественнее общих рассуждений - конкретизируйте задачу, так скать, на примере с картинками 
Киев
|
| |
|
| |
| Kazimar | Дата: Четверг, 04.03.2010, 14:18 | Сообщение # 11 |
|
Лейтенант
Группа: Пользователи
Сообщений: 67
Репутация: 3
Статус: Offline
| Есть склад досток, (допустим 20) и они разной длины. На склад приходит клиент и просит нарезать ему 5 досток по 2,5 метра. Вот необходимо расчитать кукаю доску и как разрезать, так, чтобы отходы были минимальными (так как материал дорогой). Входящими параметрами для расчета будут:
1). длина доски, необходимая для порезки;
2). Собственно количество этих досток. Есть одно ограничение. Доски не могут быть короче 1,2 метра. Тоесть резать надо так, чтобы отходы, если они будут, были длиннее 1,2 метра. В противном случае, клиент должен будет оплатить те отходы которые получаються. Понятное дело, что клиент платить за отходы не хочет поэтому их нужно минимизировать. Вот это и вся детализация задачи.
|
| |
|
| |
| Ardi | Дата: Четверг, 04.03.2010, 16:55 | Сообщение # 12 |
|
Генерал-лейтенант
Группа: Пользователи
Сообщений: 694
Репутация: 123
Статус: Offline
| Перебором всех комбинаций.
Киев .
помог - плюсуйте . icq 562128720
Сообщение отредактировал Ardi - Четверг, 04.03.2010, 17:01 |
| |
|
| |
| Kazimar | Дата: Четверг, 04.03.2010, 20:12 | Сообщение # 13 |
|
Лейтенант
Группа: Пользователи
Сообщений: 67
Репутация: 3
Статус: Offline
| Ardi, как же все комбинации пропишеш? Ведь досток то может быть разное количество и длина разная
|
| |
|
| |
| Темный_Эльф | Дата: Четверг, 04.03.2010, 21:33 | Сообщение # 14 |
|
Полковник
Группа: Пользователи
Сообщений: 173
Репутация: 33
Статус: Offline
| Берем в лоб - от первой по 2.5 сколько можно, от второй и так далее. Затем пытаемся каждую из досок заменить на одну из оставшихся. Если Н досок использовано, а М осталось, то Н*М - количество вариантов. Исходный вариант и каждый из Н*М оцениваем по отходам. Выбираем лучший. С ним повторяем то же, пока лучшим не окажется исходный. Он и есть искомый.
|
| |
|
| |
| liksoft | Дата: Пятница, 05.03.2010, 07:27 | Сообщение # 15 |
|
Полковник
Группа: Пользователи
Сообщений: 203
Репутация: 98
Статус: Offline
| Темный_Эльф, Что-то вспомнились задачки по аппроксимации из курса :).
|
| |
|
|
|
|
|
