|
Алгоритм для подбора документов с лучшей цены | ☑ | ||
---|---|---|---|---|
0
Pepeega
24.03.21
✎
14:09
|
Добрый день, возникла проблема, понадобилось написать алгоритм, который будет искать документы с более подходящими ценами, то-есть пользователь допустим вводит сумму 10 тысяч, ему из всех документов выбираются документы те, у которых общая сумма будет 10 тысяч или близкая к этой сумме, но не больше, полдня уже ломаю голову и ничего не приходит на ум, если кто-то сталкивался с проблемой буду благодарен за помощь
|
|||
1
Kassern
24.03.21
✎
14:14
|
(0) документы одного типа? Что будет правильно вернуть 2 документа по 5тыс или 1 док на 10тыс?
|
|||
2
HawkEye
24.03.21
✎
14:15
|
(0) все комбинации документов?
|
|||
3
Масянька
24.03.21
✎
14:15
|
А вы про "не могут написать функцию, которая выводит строку в обратном порядке"...
|
|||
4
Малыш Джон
24.03.21
✎
14:16
|
(0) может быть куча решений
Надо накладывать какой то критерий оптимальности(почему один набор документов лучше другого набора с такой же суммой) - и получается задача о рюкзаке. Способы решения гуглятся. |
|||
5
Pepeega
24.03.21
✎
14:17
|
(1) Да, документы одного типа, расходная накладная
(2) перебрать все документы и найти лучшую цену документов, исходя из той, которую ввел пользователь |
|||
6
Pepeega
24.03.21
✎
14:18
|
(3) ну, если вы про "перебрать документы по убыванию цены" , то это не совсем правильный подход к такой задаче
|
|||
7
piter3
24.03.21
✎
14:19
|
(5) масло масляное.Если даже критерии не можешь узнать у заказчика
|
|||
8
Pepeega
24.03.21
✎
14:19
|
(4) да вот я погуглил решения и что-то как-то не совсем понимаю, как мне перебрать эти кучи документом и найти оптимальные документы, если я допустим перебрал все документы, как я узнаю, что допустим 3 документа 900р + 5000р + 4000р лучше, чем остальные, куда сохранять все наборы документов?
|
|||
9
Pepeega
24.03.21
✎
14:21
|
(7) Заказчик указал, что ему нужно, чтобы он вводил в поле цену "Допустим 10000р", и из всех документов которые были за последний месяц, ему отобрались документы с более подходящей суммой цен = 10000р
|
|||
10
piter3
24.03.21
✎
14:22
|
(9) Ноль он дал,дальше узнавай подробности [ с более подходящей суммой цен = 10000р]
|
|||
11
Малыш Джон
24.03.21
✎
14:22
|
(9) если у тебя 1000 вариантов наборов документов и у каждого сумма = 10000, какой выбирать?
|
|||
12
Pepeega
24.03.21
✎
14:24
|
перебрать все документы не составляет труда, возникла именно проблема с построением, допустим есть всего 5 документов за месяц, сумма всех документов 18000р, первые 3 допустим общую сумму 9500 имеют, а вот другие 2 имеют общую сумму 9990р, как я узнаю, что второй вариант лучше, чем первый, мне же куда-то его сохранить нужно, а если таких документов несколько тысяч?
|
|||
13
Pepeega
24.03.21
✎
14:25
|
(11) тут не играет роль, какие документы увидит пользователь, они будут отсортированы по дате, сейчас проблема всей задачи, это правильный алгоритм, который будет находить лучшею цену
|
|||
14
yzimin
24.03.21
✎
14:25
|
(12) ну так сохраняй, в чём проблема-то?
|
|||
15
Малыш Джон
24.03.21
✎
14:26
|
(14) а так можно было??? ))
|
|||
16
Масянька
24.03.21
✎
14:27
|
(15) Не-а :)
|
|||
17
Pepeega
24.03.21
✎
14:27
|
(14) не совсем понимаю куда, вот в чем проблема, ну окей, нашел я 3 документа с общей суммой 9000р, сохраняю их в массив, их же нужно отделить как-то, чтобы сравнить потом набор разных документов
|
|||
18
Малыш Джон
24.03.21
✎
14:28
|
(13) Слушай, ну по конкретной реализации алгоритма - тут уж поднапряги мозги. Как говорят герои - "никто, кроме тебя".
|
|||
19
Масянька
24.03.21
✎
14:29
|
(18) Нормальные герои всегда идут в обход (С)
|
|||
20
yzimin
24.03.21
✎
14:29
|
(17) Новый Структура(НомерИтерации, МассивДокументов, Сумма)
|
|||
21
Pepeega
24.03.21
✎
14:30
|
(18) Тут вы правы, но на самом деле не лезет в голову момент сохранения разных наборов документов, только для этого сюда написал.
Думаю, что нужно сходить на обед и в голову придут варианты, все равно спасибо, кто откликнулся! |
|||
22
El_Duke
гуру
24.03.21
✎
14:30
|
(9) "ему отобрались документы с более подходящей суммой цен = 10000р"
Ты в 5 раз твердишь одно и тоже бессмысленное сочетание "с наиболее подходящей". Этот словесный критерий надо формализовать, положить на язык математики Нихрена не понятно что заказчик имеет ввиду под "наиболее подходящим" |
|||
23
Pepeega
24.03.21
✎
14:34
|
(22) Видимо объяснил и вправду не совсем корректно, сам имею больше информации, как и писал выше, если пользователь вводит сумму 10000р, после обхода рекурсией всех вариантов, у нас допустим в массиве получается 5 записей, 1) 8300р. 2) 9000р. 3)7800р. 4) 9800р. 5) 10000р. и мы должны будем указать вывести те документы, которые находятся в 5й записи, если бы не было 5й записи, то тогда 4, потому что она самая близкая к 10000р(введённая сумма пользователем)
|
|||
24
Pepeega
24.03.21
✎
14:36
|
(20) спасибо, как вариант подумать в эту сторону
|
|||
25
Малыш Джон
24.03.21
✎
14:43
|
(23) я конечно очень старомодный, но может не хранить все наборы, тупо на каждой итерации сравнивать сумму нового набора с суммой сохраненного ранее и если новый набор оптимальнее, то сохранять его вместо старого?
|
|||
26
Масянька
24.03.21
✎
14:44
|
(23) Запросом отобрать док-ты, у которых сумма меньше введенной (параметр + условие).
Результат запроса упорядочить по возрастанию суммы. Вывести первую запись результата запроса. |
|||
27
Злопчинский
24.03.21
✎
14:45
|
смотря сколько документов. для незначительного количества тупо перебором, отсекая варианты которые уже хуже найденных.
|
|||
28
Злопчинский
24.03.21
✎
14:46
|
лет 15 назад писал какую-то тупую хрень по тупым алгоритмам с тупыми недоработками. тупо работала.
https://infostart.ru/public/14526/ |
|||
29
Pepeega
24.03.21
✎
14:53
|
(25) с этой стороны хотел подойти, уже даже появилось полное решение, но на половине пути реализации, я понял, что первая "пачка" документов может быть 9000р, вторая 10000р, третья 8500р, четвёртая 9200р, если просто проверять, лучше наше значение чем последнее сохранённое или нет, то те самые 9000р и 10000р уже будут не в нашей видимости и мы о них не будем знать
|
|||
30
H A D G E H O G s
24.03.21
✎
14:54
|
ЦелеваяСумма=1000000;
СуммаКСписанию=ЦелеваяСумма; МассивДокументов=Новый Массив; Пока Истина Цикл Запрос=Новый Запрос; Запрос.Текст= "ВЫБРАТЬ ПЕРВЫЕ 1 | РеализацияТоваровУслуг.Ссылка КАК Ссылка, | РеализацияТоваровУслуг.СуммаДокумента КАК СуммаДокумента |ИЗ | Документ.РеализацияТоваровУслуг КАК РеализацияТоваровУслуг |ГДЕ | РеализацияТоваровУслуг.СуммаДокумента <= &СуммаКСписанию | |УПОРЯДОЧИТЬ ПО | СуммаДокумента УБЫВ"; Запрос.УстановитьПараметр("СуммаКСписанию",СуммаКСписанию); Выборка=Запрос.Выполнить().Выбрать(); Если Выборка.Количество()=0 Тогда Прервать; КонецЕсли; Выборка.Следующий(); Если Выборка.СуммаДокумента<=0 Тогда Прервать; КонецЕсли; СуммаКСписанию=СуммаКСписанию-Выборка.СуммаДокумента; МассивДокументов.Добавить(Выборка.Ссылка); Если СуммаКСписанию<=0 Тогда Прервать; КонецЕсли; КонецЦикла; |
|||
31
Pepeega
24.03.21
✎
14:55
|
(26) Тоже как вариант, но сумма может быть не 10000р, а больше, все равно придётся прибегать к алгоритму, который будет из всех полученных документом искать какую-то наилучшую общую сумму "пачки" документов
|
|||
32
H A D G E H O G s
24.03.21
✎
14:55
|
Запрос плох, в промсистеме нужно рассмотреть добавления индеска по сумме.
|
|||
33
El_Duke
гуру
24.03.21
✎
14:59
|
(29) с чего вдруг ?
Первая пачка 9000, вторая 8500, ее не храним, сравниваем с первой. Третья 10000, не храним первую ибо третья лучше. Т.о. всегда сравниваем с лучшей пачкой |
|||
34
Pepeega
24.03.21
✎
15:00
|
(30) Спасибо за пример, уже хотел прибегнуть к чему-то похожему, но стараюсь отказаться от запросов в цикле, хоть мы и выбираем 1 документ всего, но всё же, но вариант вполне рабочий, спасибо за потраченное время!
я тут подумал, что можно же один раз получить все документы, оставить только нужные и уже дальше циклом перебирать по аналогии |
|||
35
Pepeega
24.03.21
✎
15:02
|
(33) Не сразу понял такой вариант, но да, если такой вариант тоже вполне подходит для решения.
Спасибо всем кто откликнулся, думаю что-то придумать на свежую голову получится! |
|||
36
NorthWind
24.03.21
✎
15:03
|
(0) задача о рюкзаке, что ли?
|
|||
37
NorthWind
24.03.21
✎
15:03
|
ну да, она. у вас вместимость рюкзака это сумма на которую набирать, а документы - предметы.
|
|||
38
SleepyHead
гуру
24.03.21
✎
15:57
|
(0) Задача о рюкзаке.
|
|||
39
mikecool
24.03.21
✎
16:47
|
рюкзак еще не предлагали?
|
|||
40
HawkEye
24.03.21
✎
16:49
|
(39) лучше деньгами....)
|
|||
41
Pepeega
24.03.21
✎
16:50
|
да, подобие задачи о рюкзаке
(37) это понятно, осталось только с алгоритмом закончить :) |
|||
42
Малыш Джон
24.03.21
✎
16:57
|
(39) Пока нет. Думаю, надо предложить, а то никто так и не вспомнит.
|
|||
43
NorthWind
24.03.21
✎
17:01
|
а рассматривали применить что-нибудь от рюкзака? Метод ветвей и границ, динамическое программирование, еще что-нибудь? Там же куча методов, все они описаны, и, насколько я помню, не сильно сложны. Первый курс института.
|
|||
44
Pepeega
24.03.21
✎
17:06
|
(43) Да, решаю с помощью динамического программирования
|
|||
45
mistеr
24.03.21
✎
17:08
|
(43) Не торопи события. Сначала у ТС запрос, генерирующий все варианты, должен колом встать.
Потом он задумается о других методах. |
|||
46
Deal with it
24.03.21
✎
17:32
|
(0) задача рюкзака отлично решается "Динамическим программированием" из высшей математики
https://ru.wikipedia.org/wiki/Динамическое_программирование https://ru.wikipedia.org/wiki/Задача_о_рюкзаке |
|||
47
Deal with it
24.03.21
✎
17:33
|
(44) опоздал я с ответом))
|
|||
48
Михаил Козлов
24.03.21
✎
17:45
|
(41) Ваша задача немного отличается от рюкзака: нужно подобрать не максимальную сумму (без превышения лимита), а наименее отличающуюся от него.
Для рюкзака неплохо работает жадный алгоритм: - упорядочить документы по убыванию суммы; - выбирать документы в этом порядке. Если текущая сумма + сумма документа укладывается в лимит, добавить документ в массив отобранных. Может быть имеет смысл поискать более хитрый (чем жадный) алгоритм для рюкзака. Можно попробовать и метод динамического программирования, только нужно иметь в виду, что рюкзак "почти" полная переборная задача, и метод динамического программирования, вообще говоря, может привести к перебору. Метод ветвей и границ в рюкзаке не сработает: не будет эффективного отсечения. Я бы попробовал жадным алгоритмом решить 2 задачи о рюкзаке. Одна - на максимум с меньше лимита, вторая - на минимум с больше лимита. Вторую можно свести к первой заменив суммы документов на их отрицательные значения (и лимит также). |
|||
49
NorthWind
24.03.21
✎
19:00
|
(48) да, ветвей и границ здесь даст время близкое к полному перебору, непонятно как определять неоптимальность ветки.
А вот генетика тут может быть интересной. Фитнес-функция определяется легко - как раз дельта с итоговой суммой, чем меньше, тем лучше. И можно скрещивать сочетания доков, добиваясь хорошего результата. |
|||
50
Михаил Козлов
24.03.21
✎
19:39
|
(49) Генетика - буржуазная лженаука.
|
|||
51
Pepeega
25.03.21
✎
05:53
|
В общем вот что получилось, но не совсем корректно работает, потому что у меня все массивы имею значения 0, не совсем понимаю почему...
Для каждого стр из ВсеДокументы Цикл МассивДокументов.Добавить(Новый структура("ТребуемаяСумма, Сумма", ТребуемаяСумма, стр.Сумма)); КонецЦикла; МассивПроверки = Новый Массив(ТребуемаяСумма,ВсеДокументы.Количество()); Для сч = 0 по МассивДокументов[0].ТребуемаяСумма-1 Цикл МассивПроверки[сч][0] = 0; КонецЦикла; Для сч = МассивДокументов[0].ТребуемаяСумма по ВсеДокументы.Количество() Цикл МассивПроверки[сч][0] = МассивДокументов[0].Сумма; КонецЦикла; Для Счетчик = 1 по МассивДокументов.ВГраница() Цикл Для сч = 0 по МассивДокументов[Счетчик].ТребуемаяСумма-1 Цикл МассивПроверки[сч][Счетчик] = МассивПроверки[сч][Счетчик-1]; КонецЦикла; Для сч = МассивДокументов[Счетчик].ТребуемаяСумма по ВсеДокументы.Количество() Цикл МассивПроверки[сч][Счетчик] = Макс(МассивПроверки[сч][Счетчик-1], МассивПроверки[сч - МассивДокументов[Счетчик].ТребуемаяСумма][Счетчик - 1] + МассивДокументов[Счетчик].Сумма); КонецЦикла; КонецЦикла; ОставшаясяСумма = ТребуемаяСумма; МассивЛучшихДокументов = Новый Массив; ПервыйПроход = Истина; Для Х = МассивЛучшихДокументов.ВГраница() по 1 Цикл Если ПервыйПроход Тогда Если МассивПроверки[ОставшаясяСумма-1][Х+2] <> МассивПроверки[ОставшаясяСумма-1][Х+1] Тогда МассивЛучшихДокументов.Добавить(МассивДокументов[Х]); ОставшаясяСумма = ОставшаясяСумма - МассивДокументов[Х].Сумма; КонецЕсли; ПервыйПроход = Ложь; ИначеЕсли ОставшаясяСумма = ТребуемаяСумма Тогда Если МассивПроверки[ОставшаясяСумма-1][Х] <> МассивПроверки[ОставшаясяСумма-1][Х+1] Тогда МассивЛучшихДокументов.Добавить(МассивДокументов[Х]); ОставшаясяСумма = ОставшаясяСумма - МассивДокументов[Х].Сумма; КонецЕсли; Иначе Если МассивПроверки[ОставшаясяСумма][Х] <> МассивПроверки[ОставшаясяСумма][Х-1] Тогда МассивЛучшихДокументов.Добавить(МассивДокументов[Х]); ОставшаясяСумма = ОставшаясяСумма - МассивДокументов[Х].Сумма; КонецЕсли; КонецЕсли; КонецЦикла; Если МассивПроверки[ОставшаясяСумма][0] <> 0 Тогда МассивЛучшихДокументов.Добавить(МассивДокументов[0]); КонецЕсли; |
|||
52
Михаил Козлов
25.03.21
✎
17:59
|
Разбираться не стал. Вот вариант жадного алгоритма (для УФ). Предполагается, что все суммы в одной валюте.
&НаСервере Процедура ПодобратьНаСервере() Объект.Документы.Очистить(); Запрос = Новый Запрос; Запрос.Текст = "ВЫБРАТЬ | РТиУ.Ссылка КАК Ссылка, | РТиУ.СуммаДокумента КАК Сумма |ИЗ Документ.РеализацияТоваровУслуг КАК РТиУ |ГДЕ РТиУ.Дата МЕЖДУ &датаНач И &датаКон И РТиУ.СуммаДокумента<=&максСумма |УПОРЯДОЧИТЬ ПО Сумма УБЫВ"; Запрос.УстановитьПараметр("датаНач", Объект.датаНач); Запрос.УстановитьПараметр("датаКон", Объект.датаКон); Запрос.УстановитьПараметр("максСумма", Объект.ТребуемаяСумма); минВнеЛимитаРТиУ = НЕОПРЕДЕЛЕНО; суммаМинРТиУ = 0; // для не вошедшего документа с минимальной суммой подобрано = 0; выборка = Запрос.Выполнить().Выбрать(); ПОКА выборка.Следующий() Цикл Если подобрано+выборка.Сумма<Объект.ТребуемаяСумма Тогда нов = Объект.Документы.Добавить(); нов.РТиУ = выборка.Ссылка; нов.Сумма = выборка.Сумма; подобрано = подобрано+выборка.Сумма; ИначеЕсли (минВнеЛимитаРТиУ = НЕОПРЕДЕЛЕНО) ИЛИ (суммаМинРТиУ>выборка.Сумма) Тогда минВнеЛимитаРТиУ = выборка.Ссылка; суммаМинРТиУ = выборка.Сумма; КонецЕсли; КонецЦикла; // проверяем, не нужно ли включить не вошедший документ с минимальной суммой Если минВнеЛимитаРТиУ <> НЕОПРЕДЕЛЕНО И (подобрано+суммаМинРТиУ-Объект.ТребуемаяСумма<Объект.ТребуемаяСумма-подобрано) Тогда нов = Объект.Документы.Добавить(); нов.РТиУ = минВнеЛимитаРТиУ; нов.Сумма = суммаМинРТиУ; подобрано = подобрано+суммаМинРТиУ; КонецЕсли; КонецПроцедуры &НаКлиенте Процедура Подобрать(Команда) ПодобратьНаСервере(); КонецПроцедуры Могу выслать обработку (мое мыло в профиле). |
|||
53
Pepeega
02.04.21
✎
09:50
|
(52) Спасибо за пример, помог в написании!
|
Форум | Правила | Описание | Объявления | Секции | Поиск | Книга знаний | Вики-миста |