| 0
- 21.08.2014 - 09:26
|
Часто возникает задача: есть на складе куски кабеля разных длин. Надо из этого набора составить определенную длину (или чуть больше). Если решать простым перебором - по прикидкам, при 30 кусках задача займет дня два (вариантов - 1'073'741'823 на 100'000 проверок варианта уходит 15 секунд, итого 44,7 часов, хотя в реале вручную решается минут за 15, т.к. интуитивно откидываешь неправильные варианты и подбираешь практически точную длину разыскивая куски по каким-либо признакам). Смотрел алгоритмы решения задачи о ранце - все примерно об одном и том-же, что все равно придется перебирать... Может кто-то что-то подскажет попроще и побыстрее, чтоб не завязываться на интуицию?     | |
| 41
- 28.08.2014 - 08:35
| (39) и как понимать эти ряды цифр? | |
| 42
- 28.08.2014 - 09:20
|
41-bma1 > Видимо кто-то из вас что-то отбросил:) ИМХО, надо представить как действует мозг человека при ручном подборе. наверно надо сначала отбросить младшие разряды и подобрать оптимальный вариант по старшим с некоторым запасом на "хвосты". Потом добивать остаток возможными для выбранных старших разрядов хвостами. если не хватает или сильное превышение - искать соседний по старшим... | |
| 43
- 28.08.2014 - 10:03
|
Исключил повторения. 14:00:54 +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+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+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+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 14:01:52 | |
| 44
- 28.08.2014 - 10:06
|
41 - эти наборы чисел такие 1 строка - метры из твоего примера 2 строка - номера бухт " Как типичный пример: (первое значение - номер бухты, второе длина в метрах, сантиметры откидываем сразу)" | |
| 45
- 28.08.2014 - 10:13
| И тут идёт проверка на точное совпадение. Под +-% надо условия дописывать. | |
| 46
- 28.08.2014 - 10:30
| Так что, 7500 за 1 минуту все варианты, интересует? Или что-то лучше есть? | |
| 47
- 28.08.2014 - 10:53
|
2(44) понятно, буду пробовать 2(42) Понятия не имею как работает мозг ("Голова - предмет тёмный и исследованию не подлежит..." к/ф "Формула любви"). Скажу как подбирал я: сперва бессисетмный набор бухт методом тыка. Потом смотрю на получившийся результат (насколько недостает или превышает), потом на оставшиеся невыбранные позиции и через пару минут упорного гипнотизирования списка вижу кого на что менять надо (каких либо осознанных переборов вариантов не произвожу). | |
| 48
- 28.08.2014 - 11:45
| Сейчас переписал на массивы(было сначала через таблицу значений сделано) - ищет примерно 8-10 секунд. | |
| 49
- 28.08.2014 - 12:37
|
Перем Тз[100],Флаги[100],Спр[100],Список,ТзКоличествоСтрок; Процедура Показать() Стр=""; Стр1=""; Стр2=""; К1=0; Для К=1 По ТзКоличествоСтрок Цикл Стр2=Стр2+Флаги[К]; Если Флаги[К]=1 Тогда Если Стр="" Тогда Стр=Стр+Тз[К]; Стр1=Стр1+Спр[К]; Иначе Стр=Стр+"+"+Тз[К]; Стр1=Стр1+"+"+Спр[К]; КонецЕсли; К1=К1+Тз[К]; КонецЕсли; КонецЦикла; Если Список.НайтиЗначение(Стр2)=0 Тогда Сообщить(Стр+"="+К1); Сообщить(Стр1); Список.ДобавитьЗначение(Стр2) КонецЕсли; КонецПроцедуры Процедура НайтиЧисла(Остаток) Перем СтарыйОстаток; Если Остаток<=0 Тогда Возврат КонецЕсли; Для К=1 По ТзКоличествоСтрок Цикл Если Флаги[К]=1 Тогда Продолжить КонецЕсли; Если Тз[К]>Остаток Тогда Продолжить КонецЕсли; Флаги[К]=1; СтарыйОстаток=Остаток; Остаток=Остаток-Тз[К]; НайтиЧисла(Остаток); Если Остаток<=0 Тогда Возврат КонецЕсли; Флаги[К]=0; Остаток=СтарыйОстаток; КонецЦикла; КонецПроцедуры Процедура Сформировать() Список=СоздатьОбъект("СписокЗначений"); Текст=СоздатьОбъект("Текст"); Текст.Открыть("c:\ccc.txt"); ТзКоличествоСтрок=Текст.КоличествоСтрок(); Тз1=СоздатьОбъект("ТаблицаЗначений"); Тз1.НоваяКолонка("К","Число"); Тз1.НоваяКолонка("Номер","Строка"); Для К=1 По ТзКоличествоСтрок Цикл Тз1.НоваяСтрока(); Стр=Текст.ПолучитьСтроку(К); К1=Найти(Стр," "); Тз1.К=Число(Сред(Стр,К1+1)); Тз1.Номер=Лев(Стр,К1-1); КонецЦикла; Тз1.Сортировать("К-"); Для К=1 По ТзКоличествоСтрок Цикл Тз1.ПолучитьСтрокуПоНомеру(К); Тз[К]=Тз1.К; Спр[К]=Тз1.Номер; Флаги[К]=0; КонецЦикла; Сообщить(ТекущееВремя()); Остаток=Сумма; Для К=1 По ТзКоличествоСтрок Цикл Если Тз[К]>Остаток Тогда Продолжить КонецЕсли; Флаги[К]=1; Остаток=Остаток-Тз[К]; НайтиЧисла(Остаток); Если Остаток=0 Тогда Показать() КонецЕсли; Для К1=1 По ТзКоличествоСтрок Цикл Флаги[К1]=0; КонецЦикла; Остаток=Сумма; КонецЦикла; // Сообщить(ТекущееВремя()); КонецПроцедуры В текстовом файле пример, приведённый выше. | |
| 50
- 29.08.2014 - 07:06
| Это не полный перебор. Как частный случай тебе должно хватить для твоей задачи. | |
Интернет-форум Краснодарского края и Краснодара |
