Нужна помощь с алгоритмом
 

Часто возникает задача: есть на складе куски кабеля разных длин. Надо из этого набора составить определенную длину (или чуть больше).
Если решать простым перебором - по прикидкам, при 30 кусках задача займет дня два (вариантов - 1'073'741'823 на 100'000 проверок варианта уходит 15 секунд, итого 44,7 часов, хотя в реале вручную решается минут за 15, т.к. интуитивно откидываешь неправильные варианты и подбираешь практически точную длину разыскивая куски по каким-либо признакам).
Смотрел алгоритмы решения задачи о ранце - все примерно об одном и том-же, что все равно придется перебирать...
Может кто-то что-то подскажет попроще и побыстрее, чтоб не завязываться на интуицию?

1) Остатки на складе - делишь на 6 сегментов:
- Самые длинные куски, менее длинные куски, ещё более длинные куски........ самые коротенькие куски.
2) Каждому сегменту - присваиваешь "индекс дефицитности" (т.е. - чем больше штук кусков в этом сегменте - тем индекс - менее дефицитный).
3) При подборе в набор - СЕГМЕНТ ИЗ САМЫХ КОРОТЕНЬКИХ - не трогаешь. Набираешь набор из наименее дефицитных сегментов (как попало, вообще ни о чём не задумываясь, чисто по индексу дефицитности. Чтобы итоговая длина набора стала меньше требуемой на величину не менее минимального кусочка из КОРОТЕНЬКОГО сегмента) - а остаточек аккуратненько добиваешь кусочками из СЕГМЕНТА ИЗ САМЫХ КОРОТЕНЬКИХ.

- Самые длинные куски, менее длинные куски, ещё МЕНЕЕ длинные куски........ самые коротенькие куски.

это типичный "граф"

1. Подбор не должен лезть в базу (т.е. перед подбором считываем куски в динамический список).
2. Список формируем (или индексируем) от меньшего к большему.
3. "чуть больше" из алгоритма выкидываем, ибо главная задача: "сбагрить все".
4. Список "набор" формируем переносом из списка "в наличии". Признак успеха: достигнута целевая длина (>=).
Визуальную морду разбей на две вкладки: "Авто" и "Подбери сам, умник".

+4 Забыл правило после п.4:
4а. Из списка "в наличии" забираем наибольший.
Да, рекурсия.

[quote=VZ;36264105]Визуальную морду разбей на две вкладки: "Авто" и "Подбери сам, умник". [/quote]
да! да! да!
А в желтую коробочку вложить деревянные счеты!

6-bma1 > Зря иронизируешь.
Юзер сначала нажмёт "Авто", всё у него заполнится отлично.
Но твой алгоритм же не знает о том, что вон те 5 кусочков просила зарезервировать тёща гендира вчера?
Поэтому - вкладка "Подбери сам, умник" - нужна обязательно.
Для тонкого допиливания/доподбирания глазками и ручками юзера.

[quote=VZ;36264302]Из списка "в наличии" забираем наибольший.[/quote]

- Категорически не согласен. Настаиваю на том, что забирать надо не самые длинные кусочки, а наименее дефицитные по длине.

8-DeiMos > Не усложняй. Нет основания откидывать правило "кто первый встал, тому и тапки".

если побыстрому, то берём самые длинные куски и от последнего отрезаем сколько надо
или берём самые короткие куски и от последнего отрезаем сколько надо

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

[quote=DeiMos;36264382]Но твой алгоритм же не знает о том, что вон те 5 кусочков просила зарезервировать тёща гендира вчера?[/quote]
Есть заказ - значит есть резерв, нет заказа - нет резерва. С резервами как раз проблемы нет.
А подбирать "сильно больше" нельзя, т.к. клиент платит заранее, и подбирать надо под уже оплаченную длину (плюс 0-2 метра за счет компании, если куски так легли).

[quote=bma1;36264850]А подбирать "сильно больше" нельзя[/quote]

- А с чего ты взял, что мой алгоритм будет "сильно больше" подбирать? Я для чего тебе ОТДЕЛЬНО выделил сегмент с самыми короткими кусочками? Чтобы из него набор не составлялся. А только из него добивался до минимально допустимой длины.

"С резервами как раз проблемы нет."
- Бог с ними, с резервами. А как быть с излишками? Твой алгоритм же не будет знать о том, что завтра привезут 2 КамАЗа кусочков вот такой длины, и поэтому из кусочков этакой длины надо сегодня максимально срочно избавляться?

Поэтому - вкладка "Подбери сам, умник" - нужна обязательно.

[quote=DeiMos;36264997]Твой алгоритм же не будет знать о том, что завтра привезут 2 КамАЗа кусочков вот такой длины, и поэтому из кусочков этакой длины надо сегодня максимально срочно избавляться?[/quote]
А кто знает, сколько клиенту понадобится послезавтра, и какие куски не стоит трогать вообще.
Алгоритм и не должен думать. Он должен быстро и автоматически предложить вариант.

[quote=VZ;36264482]Не усложняй.[/quote]

- Этак ты по своему алгоритму - распродашь первоочерёдно все самые большие и просто большие куски. Останешься торговать только короткими и самыми короткими.

[quote=DeiMos;36265112]Алгоритм и не должен думать. Он должен быстро и автоматически предложить вариант. [/quote]

- Именно об этом я тебе и толкую.
А думать - пусть думает вкладка "Подбери сам, умник".

0-bma1 > На здоровье. Рады были тебе помочь советом. Заходи есчо.

Конечно, все зависит от количества кусков на складе. Но я бы попробовал так: заранее рассчитываем и храним всевозможные наборы из двух кусков и из трех. Максимальную длину трех кусков назовем М. Приходит заказ на длину Д. Если Д<М берем наиболее подходящий по длине кусок или набор, если тут ничего не подошло, то подбираем ручками. Если Д>М начинаем собирать с самых длинных, пока не приблизимся к результату на длину меньше М и возвращаемся к первой части алгоритма.

фуфло гоняете.

Частенько при покупке клиент накладывает ограничение на

- [b]минимальную длину[/b] куска (правила запрещают сращивать провод при прокладке)

-[b]кратность куска определенному метражу[/b] (для уменьшения своих потерь)


Алгоритм деймоса даст либо накопление огрызков провода непотребной длины (к примру, куски по 1-2 метра мало кому нужны на производство, только частнику и то исключительно редко). Продать же провод кусками - далеко не каждый покупатель согласится его взять.

Чтобы алгоритм как то работал - необходимо при продаже действовать по принципу, если остаток в мотке меньше X метров, то либо отрезать от другого мотка, либо клиент забирает весь остаток.

Х определяется га основании спроса для каждого типа провода (толщина, изоляция и т.д).

Без доп ограничений при продаже будет постепенное затоваривание маленькими огрызками провода

18-Helen1986 > по этой причине, обычно продают минимальную единицу измерения - бухту. и дополнительно предоставляют сервис по нарезке кабеля. бывают ну оочень толстые кабели, которые так просто не отрежешь, не доставишь, и не проложишь.

(0) Какие действия программы ожидаются в том случае, если абсолютно точного подбора достичь невозможно?
Например, есть 30 кусков кабеля длиной от 1 до 30, а заказана длина 19.5 метров - программа должна просто сообщить "нет вариантов", или сделать что-то ещё?

20-Пудель > там в условии "или чуть больше"

21-Зелёный тролль > Только вот это "чуть" надо оцифровать ;) Т.е., написать [em]Функция Чуть(х) Экспорт[/em]
:)

Я к тому, что, может, переформулировать условие с "или чуть больше" до "или больше, но как можно меньше"? :)
И ещё, было бы интересно поэкспериментировать с конкретными наборами значений, bma1, можно ли конкретные наборы длин и заказанные длины, как тестовые примеры?

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 м.

И доплачивать не будет, т.е. максимум можем ему пару-тройку метров "подарить". Кабель не резать, т.к. отрезка тоже денег приличных стоит и на складе упрутся рогом, если отрезку в наряд не включат.
P.S. решение вручную ищется минут за 5-10, с точным количеством метража.

Алгоритм з-адача о рюкзаке - считает быстро.
у меня аналогичным образом мегапоставка подсчитывает скольо палет получится приукладке на палету кучей - только вместо длин - объемы и ограничение - объемом палеты. На 300-500 артикулов - 14-30 палет считается практически очень быстро - задержек нет

[quote=Чучундер;36303512]у меня аналогичным образом мегапоставка подсчитывает скольо палет получится приукладке на палету кучей [/quote]
Каким вариантом алгоритма пользуешься?

(27) на мисте NS в свое время публиковал (работат на рекурсии) - немного допилил (не без огрехов) - но фурычит.

писал давным давно, в код уже фиг знает когда заглядывал... Думаю если наложить на подбор отрезка дополнительные условия - то получится ваще что надо.

вот примерно вот так это выглядит [url]http://screencast.com/t/hBHfxBu9[/url]

24-bma1 > каждой бухты по 1 шт? требования к длине кусков у покупателя отсутствуют? желания списывать те бухты, которых больше в наличии, у продавца отсутствует?

2(31) да, требования у покупателя - чем куски больше тем ему лучше, но есть требования и у нашей стороны - бери что дают. если удастся всучить коротыши - значит очень хорошо. куски должны быть целыми и превышение длины не более 0.1% от общей оплаченой длины. Стоимость отрезки высока - т.к. под участок отрезки надо освобождать на складе место, разматывать бухты, перемерять, и т.п. - кучу народа привлекать.

(32) Так чего проще... Отсортируй куски по длине от меньшей к большей и набирай.

33-Pasha_Kom > Для тех кто в танке: делать монтаж километровой магистрали из кусков по 10 метров - это идиотизм.

(32) алгоритм в (30) подберет нормально.
.
"куски должны быть целыми и превышение длины не более 0.1% от общей оплаченой длины." - в общем случае нерешаемо.

[url]http://opennotes.ru/knowledge/vba-knowledge/algoritm-poiska-vsex-kombinacij-chisel-dayushhix-zadannuyu-summu-na-vba/[/url]
Посмотри, если ещё не видел.

Алгоритм поиска всех комбинаций чисел дающих заданную сумму (на VBA)
7 Апрель 2013, VBA, Konstantin

Сделал алгоритм, по поиску заданной суммы, для твоего примера нашло вот это набор.
12:01:26
+617+615+615+615+615+615+614+613+613+613+612+411+276+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

Нашёл ошибку, это был поиск первой попавшейся комбинации. Посмотрим, сколько будет всё искать.

12:30:56
+617+615+615+615+615+615+614+613+613+613+612+411+276+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+276+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+276+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+276+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+276+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+276+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+276+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+276+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+276+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+276+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+276+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+125+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+276+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+276+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+125+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+276+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+276+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+309+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+309+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+276+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+261+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+125+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+276+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+125+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+125+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+276+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+309+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+309+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+125+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