| 0
- 21.08.2014 - 09:26
|
Часто возникает задача: есть на складе куски кабеля разных длин. Надо из этого набора составить определенную длину (или чуть больше). Если решать простым перебором - по прикидкам, при 30 кусках задача займет дня два (вариантов - 1'073'741'823 на 100'000 проверок варианта уходит 15 секунд, итого 44,7 часов, хотя в реале вручную решается минут за 15, т.к. интуитивно откидываешь неправильные варианты и подбираешь практически точную длину разыскивая куски по каким-либо признакам). Смотрел алгоритмы решения задачи о ранце - все примерно об одном и том-же, что все равно придется перебирать... Может кто-то что-то подскажет попроще и побыстрее, чтоб не завязываться на интуицию?     | | |
| 1
- 21.08.2014 - 10:00
|
1) Остатки на складе - делишь на 6 сегментов: - Самые длинные куски, менее длинные куски, ещё более длинные куски........ самые коротенькие куски. 2) Каждому сегменту - присваиваешь "индекс дефицитности" (т.е. - чем больше штук кусков в этом сегменте - тем индекс - менее дефицитный). 3) При подборе в набор - СЕГМЕНТ ИЗ САМЫХ КОРОТЕНЬКИХ - не трогаешь. Набираешь набор из наименее дефицитных сегментов (как попало, вообще ни о чём не задумываясь, чисто по индексу дефицитности. Чтобы итоговая длина набора стала меньше требуемой на величину не менее минимального кусочка из КОРОТЕНЬКОГО сегмента) - а остаточек аккуратненько добиваешь кусочками из СЕГМЕНТА ИЗ САМЫХ КОРОТЕНЬКИХ. | | |
| 2
- 21.08.2014 - 10:01
| - Самые длинные куски, менее длинные куски, ещё МЕНЕЕ длинные куски........ самые коротенькие куски. | | |
| 3
- 21.08.2014 - 10:01
| это типичный "граф" | | |
| 4
- 21.08.2014 - 10:08
|
1. Подбор не должен лезть в базу (т.е. перед подбором считываем куски в динамический список). 2. Список формируем (или индексируем) от меньшего к большему. 3. "чуть больше" из алгоритма выкидываем, ибо главная задача: "сбагрить все". 4. Список "набор" формируем переносом из списка "в наличии". Признак успеха: достигнута целевая длина (>=). Визуальную морду разбей на две вкладки: "Авто" и "Подбери сам, умник". | | |
| 5
- 21.08.2014 - 10:18
|
+4 Забыл правило после п.4: 4а. Из списка "в наличии" забираем наибольший. Да, рекурсия. | | |
| 6
- 21.08.2014 - 10:18
| Цитата:
А в желтую коробочку вложить деревянные счеты! | | |
| 7
- 21.08.2014 - 10:22
|
6-bma1 > Зря иронизируешь. Юзер сначала нажмёт "Авто", всё у него заполнится отлично. Но твой алгоритм же не знает о том, что вон те 5 кусочков просила зарезервировать тёща гендира вчера? Поэтому - вкладка "Подбери сам, умник" - нужна обязательно. Для тонкого допиливания/доподбирания глазками и ручками юзера. | | |
| 8
- 21.08.2014 - 10:24
| Цитата:
| | |
| 9
- 21.08.2014 - 10:28
| 8-DeiMos > Не усложняй. Нет основания откидывать правило "кто первый встал, тому и тапки". | | |
| 10
- 21.08.2014 - 10:34
|
если побыстрому, то берём самые длинные куски и от последнего отрезаем сколько надо или берём самые короткие куски и от последнего отрезаем сколько надо если резать нельзя, то один раз рассчитать все возможные варианты суммарных длин всех наборов кусков, и перемерять при поступлении/выбытии той или иной длины, можно регламентом по ночам. а днём, если в течении текущего дня что-то куда-то ушло, то брать ближайшее значение подлиннее. | | |
| 11
- 21.08.2014 - 10:50
| Цитата:
А подбирать "сильно больше" нельзя, т.к. клиент платит заранее, и подбирать надо под уже оплаченную длину (плюс 0-2 метра за счет компании, если куски так легли). | | |
| 12
- 21.08.2014 - 10:59
| Цитата:
"С резервами как раз проблемы нет." - Бог с ними, с резервами. А как быть с излишками? Твой алгоритм же не будет знать о том, что завтра привезут 2 КамАЗа кусочков вот такой длины, и поэтому из кусочков этакой длины надо сегодня максимально срочно избавляться? Поэтому - вкладка "Подбери сам, умник" - нужна обязательно. | | |
| 13
- 21.08.2014 - 11:06
| Цитата:
Алгоритм и не должен думать. Он должен быстро и автоматически предложить вариант. | | |
| 14
- 21.08.2014 - 11:06
| Цитата:
| | |
| 15
- 21.08.2014 - 11:08
| Цитата:
А думать - пусть думает вкладка "Подбери сам, умник". | | |
| 16
- 22.08.2014 - 08:22
| 0-bma1 > На здоровье. Рады были тебе помочь советом. Заходи есчо. | | |
| 17
- 23.08.2014 - 18:16
| Конечно, все зависит от количества кусков на складе. Но я бы попробовал так: заранее рассчитываем и храним всевозможные наборы из двух кусков и из трех. Максимальную длину трех кусков назовем М. Приходит заказ на длину Д. Если Д<М берем наиболее подходящий по длине кусок или набор, если тут ничего не подошло, то подбираем ручками. Если Д>М начинаем собирать с самых длинных, пока не приблизимся к результату на длину меньше М и возвращаемся к первой части алгоритма. | | |
| 18
- 23.08.2014 - 19:12
|
фуфло гоняете. Частенько при покупке клиент накладывает ограничение на - минимальную длину куска (правила запрещают сращивать провод при прокладке) -кратность куска определенному метражу (для уменьшения своих потерь) Алгоритм деймоса даст либо накопление огрызков провода непотребной длины (к примру, куски по 1-2 метра мало кому нужны на производство, только частнику и то исключительно редко). Продать же провод кусками - далеко не каждый покупатель согласится его взять. Чтобы алгоритм как то работал - необходимо при продаже действовать по принципу, если остаток в мотке меньше X метров, то либо отрезать от другого мотка, либо клиент забирает весь остаток. Х определяется га основании спроса для каждого типа провода (толщина, изоляция и т.д). Без доп ограничений при продаже будет постепенное затоваривание маленькими огрызками провода | | |
| 19
- 23.08.2014 - 22:43
| 18-Helen1986 > по этой причине, обычно продают минимальную единицу измерения - бухту. и дополнительно предоставляют сервис по нарезке кабеля. бывают ну оочень толстые кабели, которые так просто не отрежешь, не доставишь, и не проложишь. | | |
| 20
- 24.08.2014 - 19:17
|
(0) Какие действия программы ожидаются в том случае, если абсолютно точного подбора достичь невозможно? Например, есть 30 кусков кабеля длиной от 1 до 30, а заказана длина 19.5 метров - программа должна просто сообщить "нет вариантов", или сделать что-то ещё? | | |
| 21
- 24.08.2014 - 19:21
| 20-Пудель > там в условии "или чуть больше" | | |
| 22
- 24.08.2014 - 21:12
|
21-Зелёный тролль > Только вот это "чуть" надо оцифровать ;) Т.е., написать Функция Чуть(х) Экспорт :) | | |
| 23
- 24.08.2014 - 21:49
|
Я к тому, что, может, переформулировать условие с "или чуть больше" до "или больше, но как можно меньше"? :) И ещё, было бы интересно поэкспериментировать с конкретными наборами значений, bma1, можно ли конкретные наборы длин и заказанные длины, как тестовые примеры? | | |
| 24
- 25.08.2014 - 09:01
|
2(23) Как типичный пример: (первое значение - номер бухты, второе длина в метрах, сантиметры откидываем сразу) 128-315 613,000 128-316 613,000 128-317 615,000 128-318 610,000 128-319 55,000 128-320 125,000 128-321 63,000 128-322 117,000 128-323 612,000 128-324 614,000 128-325 615,000 128-326 611,000 128-327 56,000 128-328 554,000 128-329 615,000 128-330 609,000 128-331 116,000 128-332 411,000 128-333 30,000 128-334 615,000 128-335 613,000 128-336 615,000 128-337 28,000 128-338 276,000 128-339 309,000 128-340 610,000 128-341 617,000 128-342 261,000 128-343 350,000 Покупатель олатил 7500 м. | | |
| 25
- 25.08.2014 - 09:04
|
И доплачивать не будет, т.е. максимум можем ему пару-тройку метров "подарить". Кабель не резать, т.к. отрезка тоже денег приличных стоит и на складе упрутся рогом, если отрезку в наряд не включат. P.S. решение вручную ищется минут за 5-10, с точным количеством метража. | | |
| 26
- 25.08.2014 - 15:12
|
Алгоритм з-адача о рюкзаке - считает быстро. у меня аналогичным образом мегапоставка подсчитывает скольо палет получится приукладке на палету кучей - только вместо длин - объемы и ограничение - объемом палеты. На 300-500 артикулов - 14-30 палет считается практически очень быстро - задержек нет | | |
| 27
- 25.08.2014 - 21:04
| Цитата:
| | |
| 28
- 26.08.2014 - 08:42
| (27) на мисте NS в свое время публиковал (работат на рекурсии) - немного допилил (не без огрехов) - но фурычит. | | |
| 29
- 26.08.2014 - 08:44
| писал давным давно, в код уже фиг знает когда заглядывал... Думаю если наложить на подбор отрезка дополнительные условия - то получится ваще что надо. | | |
| 30
- 26.08.2014 - 09:05
| вот примерно вот так это выглядит http://screencast.com/t/hBHfxBu9 | | |
| 31
- 26.08.2014 - 12:27
| 24-bma1 > каждой бухты по 1 шт? требования к длине кусков у покупателя отсутствуют? желания списывать те бухты, которых больше в наличии, у продавца отсутствует? | | |
| 32
- 26.08.2014 - 12:54
| 2(31) да, требования у покупателя - чем куски больше тем ему лучше, но есть требования и у нашей стороны - бери что дают. если удастся всучить коротыши - значит очень хорошо. куски должны быть целыми и превышение длины не более 0.1% от общей оплаченой длины. Стоимость отрезки высока - т.к. под участок отрезки надо освобождать на складе место, разматывать бухты, перемерять, и т.п. - кучу народа привлекать. | | |
| 33
- 26.08.2014 - 14:01
| (32) Так чего проще... Отсортируй куски по длине от меньшей к большей и набирай. | | |
| 34
- 26.08.2014 - 16:17
| 33-Pasha_Kom > Для тех кто в танке: делать монтаж километровой магистрали из кусков по 10 метров - это идиотизм. | | |
| 35
- 26.08.2014 - 19:05
|
(32) алгоритм в (30) подберет нормально. . "куски должны быть целыми и превышение длины не более 0.1% от общей оплаченой длины." - в общем случае нерешаемо. | | |
| 36
- 28.08.2014 - 06:55
| http://opennotes.ru/knowledge/vba-kn...-summu-na-vba/ Посмотри, если ещё не видел. Алгоритм поиска всех комбинаций чисел дающих заданную сумму (на VBA) 7 Апрель 2013, VBA, Konstantin | | |
| 37
- 28.08.2014 - 08:01
|
Сделал алгоритм, по поиску заданной суммы, для твоего примера нашло вот это набор. 12:01:26 +617+615+615+615+615+615+614+613+613+613+612+411+2 76+56 +128-341+128-336+128-317+128-334+128-329+128-325+128-324+128-335+128-315+128-316+128-323+128-332+128-338+128-327 12:01:26 | | |
| 38
- 28.08.2014 - 08:32
| Нашёл ошибку, это был поиск первой попавшейся комбинации. Посмотрим, сколько будет всё искать. | | |
| 39
- 28.08.2014 - 08:32
|
12:30:56 +617+615+615+615+615+615+614+613+613+613+612+411+2 76+56 +128-341+128-336+128-317+128-334+128-329+128-325+128-324+128-335+128-315+128-316+128-323+128-332+128-338+128-327 +617+615+615+615+615+615+614+613+613+613+612+411+2 76+56 +128-341+128-336+128-317+128-334+128-329+128-325+128-324+128-335+128-315+128-316+128-323+128-332+128-338+128-327 +617+615+615+615+615+615+614+613+613+613+612+411+2 76+56 +128-341+128-336+128-317+128-334+128-329+128-325+128-324+128-335+128-315+128-316+128-323+128-332+128-338+128-327 +617+615+615+615+615+615+614+613+613+613+612+411+2 76+56 +128-341+128-336+128-317+128-334+128-329+128-325+128-324+128-335+128-315+128-316+128-323+128-332+128-338+128-327 +617+615+615+615+615+615+614+613+613+613+612+411+2 76+56 +128-341+128-336+128-317+128-334+128-329+128-325+128-324+128-335+128-315+128-316+128-323+128-332+128-338+128-327 +617+615+615+615+615+615+614+613+613+613+612+411+2 76+56 +128-341+128-336+128-317+128-334+128-329+128-325+128-324+128-335+128-315+128-316+128-323+128-332+128-338+128-327 +617+615+615+615+615+615+614+613+613+613+612+411+2 76+56 +128-341+128-336+128-317+128-334+128-329+128-325+128-324+128-335+128-315+128-316+128-323+128-332+128-338+128-327 +617+615+615+615+615+615+614+613+613+613+612+411+2 76+56 +128-341+128-336+128-317+128-334+128-329+128-325+128-324+128-335+128-315+128-316+128-323+128-332+128-338+128-327 +617+615+615+615+615+615+614+613+613+613+612+411+2 76+56 +128-341+128-336+128-317+128-334+128-329+128-325+128-324+128-335+128-315+128-316+128-323+128-332+128-338+128-327 +617+615+615+615+615+615+614+613+613+613+612+411+2 76+56 +128-341+128-336+128-317+128-334+128-329+128-325+128-324+128-335+128-315+128-316+128-323+128-332+128-338+128-327 +617+615+615+615+615+615+614+613+613+613+612+411+2 76+56 +128-341+128-336+128-317+128-334+128-329+128-325+128-324+128-335+128-315+128-316+128-323+128-332+128-338+128-327 +617+615+615+615+615+615+614+613+613+613+611+411+1 25+117+63+28 +128-341+128-336+128-317+128-334+128-329+128-325+128-324+128-335+128-315+128-316+128-326+128-332+128-320+128-322+128-321+128-337 +617+615+615+615+615+615+614+613+613+613+610+411+2 76+30+28 +128-341+128-336+128-317+128-334+128-329+128-325+128-324+128-335+128-315+128-316+128-340+128-332+128-338+128-333+128-337 +617+615+615+615+615+615+614+613+613+613+610+411+2 76+30+28 +128-341+128-336+128-317+128-334+128-329+128-325+128-324+128-335+128-315+128-316+128-318+128-332+128-338+128-333+128-337 +617+615+615+615+615+615+614+613+613+613+609+411+1 25+117+63+30 +128-341+128-336+128-317+128-334+128-329+128-325+128-324+128-335+128-315+128-316+128-330+128-332+128-320+128-322+128-321+128-333 +617+615+615+615+615+615+614+613+613+613+554+411+2 76+56+30+28 +128-341+128-336+128-317+128-334+128-329+128-325+128-324+128-335+128-315+128-316+128-328+128-332+128-338+128-327+128-333+128-337 +617+615+615+615+615+615+614+613+613+613+612+411+2 76+56 +128-341+128-336+128-317+128-334+128-329+128-325+128-324+128-335+128-315+128-316+128-323+128-332+128-338+128-327 +617+615+615+615+615+615+614+613+613+613+612+350+3 09+56+28 +128-341+128-336+128-317+128-334+128-329+128-325+128-324+128-335+128-315+128-316+128-323+128-343+128-339+128-327+128-337 +617+615+615+615+615+615+614+613+613+613+612+350+3 09+56+28 +128-341+128-336+128-317+128-334+128-329+128-325+128-324+128-335+128-315+128-316+128-323+128-343+128-339+128-327+128-337 +617+615+615+615+615+615+614+613+613+613+612+411+2 76+56 +128-341+128-336+128-317+128-334+128-329+128-325+128-324+128-335+128-315+128-316+128-323+128-332+128-338+128-327 +617+615+615+615+615+615+614+613+613+613+612+309+2 61+117+56 +128-341+128-336+128-317+128-334+128-329+128-325+128-324+128-335+128-315+128-316+128-323+128-339+128-342+128-322+128-327 +617+615+615+615+615+615+614+613+613+613+612+411+1 25+116+63+28 +128-341+128-336+128-317+128-334+128-329+128-325+128-324+128-335+128-315+128-316+128-323+128-332+128-320+128-331+128-321+128-337 +617+615+615+615+615+615+614+613+613+613+612+350+2 76+117 +128-341+128-336+128-317+128-334+128-329+128-325+128-324+128-335+128-315+128-316+128-323+128-343+128-338+128-322 +617+615+615+615+615+615+614+613+613+613+612+411+1 25+116+63+28 +128-341+128-336+128-317+128-334+128-329+128-325+128-324+128-335+128-315+128-316+128-323+128-332+128-320+128-331+128-321+128-337 +617+615+615+615+615+615+614+613+613+613+612+411+1 25+116+63+28 +128-341+128-336+128-317+128-334+128-329+128-325+128-324+128-335+128-315+128-316+128-323+128-332+128-320+128-331+128-321+128-337 +617+615+615+615+615+615+614+613+613+613+612+411+2 76+56 +128-341+128-336+128-317+128-334+128-329+128-325+128-324+128-335+128-315+128-316+128-323+128-332+128-338+128-327 +617+615+615+615+615+615+614+613+613+613+611+350+3 09+55+30 +128-341+128-336+128-317+128-334+128-329+128-325+128-324+128-335+128-315+128-316+128-326+128-343+128-339+128-319+128-333 +617+615+615+615+615+615+614+613+613+613+611+350+3 09+55+30 +128-341+128-336+128-317+128-334+128-329+128-325+128-324+128-335+128-315+128-316+128-326+128-343+128-339+128-319+128-333 +617+615+615+615+615+615+614+613+613+613+612+411+1 25+116+63+28 +128-341+128-336+128-317+128-334+128-329+128-325+128-324+128-335+128-315+128-316+128-323+128-332+128-320+128-331+128-321+128-337 12:31:53 | |
Интернет-форум Краснодарского края и Краснодара |
