Вход | Регистрация
 

Алгоритм для подбора документов с лучшей цены

Алгоритм для подбора документов с лучшей цены
Я
   Pepeega
 
24.03.21 - 14:09
Добрый день, возникла проблема, понадобилось написать алгоритм, который будет искать документы с более подходящими ценами, то-есть пользователь допустим вводит сумму 10 тысяч, ему из всех документов выбираются документы те, у которых общая сумма будет 10 тысяч или близкая к этой сумме, но не больше, полдня уже ломаю голову и ничего не приходит на ум, если кто-то сталкивался с проблемой буду благодарен за помощь
   Kassern
 
1 - 24.03.21 - 14:14
(0) документы одного типа? Что будет правильно вернуть 2 документа по 5тыс или 1 док на 10тыс?
   HawkEye
 
2 - 24.03.21 - 14:15
(0) все комбинации документов?
   Масянька
 
3 - 24.03.21 - 14:15
А вы про "не могут написать функцию, которая выводит строку в обратном порядке"...
   Малыш Джон
 
4 - 24.03.21 - 14:16
(0) может быть куча решений

Надо накладывать какой то критерий оптимальности(почему один набор документов лучше другого набора с такой же суммой) - и получается задача о рюкзаке. Способы решения гуглятся.
   Pepeega
 
5 - 24.03.21 - 14:17
(1) Да, документы одного типа, расходная накладная
(2) перебрать все документы и найти лучшую цену документов, исходя из той, которую ввел пользователь
   Pepeega
 
6 - 24.03.21 - 14:18
(3) ну, если вы про "перебрать документы по убыванию цены" , то это не совсем правильный подход к такой задаче
   piter3
 
7 - 24.03.21 - 14:19
(5) масло масляное.Если даже критерии не можешь узнать у заказчика
   Pepeega
 
8 - 24.03.21 - 14:19
(4) да вот я погуглил решения и что-то как-то не совсем понимаю, как мне перебрать эти кучи документом и найти оптимальные документы, если я допустим перебрал все документы, как я узнаю, что допустим 3 документа 900р + 5000р + 4000р лучше, чем остальные, куда сохранять все наборы документов?
   Pepeega
 
9 - 24.03.21 - 14:21
(7) Заказчик указал, что ему нужно, чтобы он вводил в поле цену "Допустим 10000р", и из всех документов которые были за последний месяц, ему отобрались документы с более подходящей суммой цен = 10000р
   piter3
 
10 - 24.03.21 - 14:22
(9) Ноль он дал,дальше узнавай подробности [ с более подходящей суммой цен = 10000р]
   Малыш Джон
 
11 - 24.03.21 - 14:22
(9) если у тебя 1000 вариантов наборов документов и у каждого сумма = 10000, какой выбирать?
   Pepeega
 
12 - 24.03.21 - 14:24
перебрать все документы не составляет труда, возникла именно проблема с построением, допустим есть всего 5 документов за месяц, сумма всех документов 18000р, первые 3 допустим общую сумму 9500 имеют, а вот другие 2 имеют общую сумму 9990р, как я узнаю, что второй вариант лучше, чем первый, мне же куда-то его сохранить нужно, а если таких документов несколько тысяч?
   Pepeega
 
13 - 24.03.21 - 14:25
(11) тут не играет роль, какие документы увидит пользователь, они будут отсортированы по дате, сейчас проблема всей задачи, это правильный алгоритм, который будет находить лучшею цену
   yzimin
 
14 - 24.03.21 - 14:25
(12) ну так сохраняй, в чём проблема-то?
   Малыш Джон
 
15 - 24.03.21 - 14:26
(14) а так можно было??? ))
   Масянька
 
16 - 24.03.21 - 14:27
(15) Не-а :)
   Pepeega
 
17 - 24.03.21 - 14:27
(14) не совсем понимаю куда, вот в чем проблема, ну окей, нашел я 3 документа с общей суммой 9000р, сохраняю их в массив, их же нужно отделить как-то, чтобы сравнить потом набор разных документов
   Малыш Джон
 
18 - 24.03.21 - 14:28
(13) Слушай, ну по конкретной реализации алгоритма - тут уж поднапряги мозги. Как говорят герои - "никто, кроме тебя".
   Масянька
 
19 - 24.03.21 - 14:29
(18) Нормальные герои всегда идут в обход (С)
   yzimin
 
20 - 24.03.21 - 14:29
(17) Новый Структура(НомерИтерации, МассивДокументов, Сумма)
   Pepeega
 
21 - 24.03.21 - 14:30
(18) Тут вы правы, но на самом деле не лезет в голову момент сохранения разных наборов документов, только для этого сюда написал.

Думаю, что нужно сходить на обед и в голову придут варианты, все равно спасибо, кто откликнулся!
   El_Duke
 
22 - 24.03.21 - 14:30
(9) "ему отобрались документы с более подходящей суммой цен = 10000р"

Ты в 5 раз твердишь одно и тоже бессмысленное сочетание "с наиболее подходящей". Этот словесный критерий надо формализовать, положить на язык математики
Нихрена не понятно что заказчик имеет ввиду под "наиболее подходящим"
   Pepeega
 
23 - 24.03.21 - 14:34
(22) Видимо объяснил и вправду не совсем корректно, сам имею больше информации, как и писал выше, если пользователь вводит сумму 10000р, после обхода рекурсией всех вариантов, у нас допустим в массиве получается 5 записей, 1) 8300р. 2) 9000р. 3)7800р. 4) 9800р. 5) 10000р. и мы должны будем указать вывести те документы, которые находятся в 5й записи, если бы не было 5й записи, то тогда 4, потому что она самая близкая к 10000р(введённая сумма пользователем)
   Pepeega
 
24 - 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/
   Pepeega
 
29 - 24.03.21 - 14:53
(25) с этой стороны хотел подойти, уже даже появилось полное решение, но на половине пути реализации, я понял, что первая "пачка" документов может быть 9000р, вторая 10000р, третья 8500р, четвёртая 9200р, если просто проверять, лучше наше значение чем последнее сохранённое или нет, то те самые 9000р и 10000р уже будут не в нашей видимости и мы о них не будем знать
   H A D G E H O G s
 
30 - 24.03.21 - 14:54
ЦелеваяСумма=1000000;
    СуммаКСписанию=ЦелеваяСумма;
    МассивДокументов=Новый Массив;
    Пока Истина Цикл
        Запрос=Новый Запрос;
        Запрос.Текст=
        "ВЫБРАТЬ ПЕРВЫЕ 1
        |    РеализацияТоваровУслуг.Ссылка КАК Ссылка,
        |    РеализацияТоваровУслуг.СуммаДокумента КАК СуммаДокумента
        |ИЗ
        |    Документ.РеализацияТоваровУслуг КАК РеализацияТоваровУслуг
        |ГДЕ
        |    РеализацияТоваровУслуг.СуммаДокумента <= &СуммаКСписанию
        |
        |УПОРЯДОЧИТЬ ПО
        |    СуммаДокумента УБЫВ";
        Запрос.УстановитьПараметр("СуммаКСписанию",СуммаКСписанию);
        Выборка=Запрос.Выполнить().Выбрать();
        Если Выборка.Количество()=0 Тогда
            Прервать;
        КонецЕсли;
        Выборка.Следующий();
        Если Выборка.СуммаДокумента<=0 Тогда
            Прервать;
        КонецЕсли;
        
        СуммаКСписанию=СуммаКСписанию-Выборка.СуммаДокумента;
        МассивДокументов.Добавить(Выборка.Ссылка);
        Если СуммаКСписанию<=0 Тогда
            Прервать;
        КонецЕсли;        
    КонецЦикла;
 
 
   Pepeega
 
31 - 24.03.21 - 14:55
(26) Тоже как вариант, но сумма может быть не 10000р, а больше, все равно придётся прибегать к алгоритму, который будет из всех полученных документом искать какую-то наилучшую общую сумму "пачки" документов
   H A D G E H O G s
 
32 - 24.03.21 - 14:55
Запрос плох, в промсистеме нужно рассмотреть добавления индеска по сумме.
   El_Duke
 
33 - 24.03.21 - 14:59
(29) с чего вдруг ?
Первая пачка 9000, вторая 8500, ее не храним, сравниваем с первой. Третья 10000, не храним первую ибо третья лучше. Т.о. всегда сравниваем с лучшей пачкой
   Pepeega
 
34 - 24.03.21 - 15:00
(30) Спасибо за пример, уже хотел прибегнуть к чему-то похожему, но стараюсь отказаться от запросов в цикле, хоть мы и выбираем 1 документ всего, но всё же, но вариант вполне рабочий, спасибо за потраченное время!
я тут подумал, что можно же один раз получить все документы, оставить только нужные и уже дальше циклом перебирать по аналогии
   Pepeega
 
35 - 24.03.21 - 15:02
(33) Не сразу понял такой вариант, но да, если такой вариант тоже вполне подходит для решения.

Спасибо всем кто откликнулся, думаю что-то придумать на свежую голову получится!
   NorthWind
 
36 - 24.03.21 - 15:03
(0) задача о рюкзаке, что ли?
   NorthWind
 
37 - 24.03.21 - 15:03
ну да, она. у вас вместимость рюкзака это сумма на которую набирать, а документы - предметы.
   SleepyHead
 
38 - 24.03.21 - 15:57
(0) Задача о рюкзаке.
   mikecool
 
39 - 24.03.21 - 16:47
рюкзак еще не предлагали?
   HawkEye
 
40 - 24.03.21 - 16:49
(39) лучше деньгами....)
   Pepeega
 
41 - 24.03.21 - 16:50
да, подобие задачи о рюкзаке
(37) это понятно, осталось только с алгоритмом закончить :)
   Малыш Джон
 
42 - 24.03.21 - 16:57
(39) Пока нет. Думаю, надо предложить, а то никто так и не вспомнит.
   NorthWind
 
43 - 24.03.21 - 17:01
а рассматривали применить что-нибудь от рюкзака? Метод ветвей и границ, динамическое программирование, еще что-нибудь? Там же куча методов, все они описаны, и, насколько я помню, не сильно сложны. Первый курс института.
   Pepeega
 
44 - 24.03.21 - 17:06
(43) Да, решаю с помощью динамического программирования
   mistеr
 
45 - 24.03.21 - 17:08
(43) Не торопи события. Сначала у ТС запрос, генерирующий все варианты, должен колом встать.
Потом он задумается о других методах.
   Deal with it
 
46 - 24.03.21 - 17:32
(0) задача рюкзака отлично решается "Динамическим программированием" из высшей математики
https://ru.wikipedia.org/wiki/Динамическое_программирование

https://ru.wikipedia.org/wiki/Задача_о_рюкзаке
   Deal with it
 
47 - 24.03.21 - 17:33
(44) опоздал я с ответом))
   Михаил Козлов
 
48 - 24.03.21 - 17:45
(41) Ваша задача немного отличается от рюкзака: нужно подобрать не максимальную сумму (без превышения лимита), а наименее отличающуюся от него.
Для рюкзака неплохо работает жадный алгоритм:
- упорядочить документы по убыванию суммы;
- выбирать документы в этом порядке. Если текущая сумма + сумма документа укладывается в лимит, добавить документ в массив отобранных.
Может быть имеет смысл поискать более хитрый (чем жадный) алгоритм для рюкзака. Можно попробовать и метод динамического программирования, только нужно иметь в виду, что рюкзак "почти" полная переборная задача, и метод динамического программирования, вообще говоря, может привести к перебору. Метод ветвей и границ в рюкзаке не сработает: не будет эффективного отсечения.
Я бы попробовал жадным алгоритмом решить 2 задачи о рюкзаке. Одна - на максимум с меньше лимита, вторая - на минимум с больше лимита. Вторую можно свести к первой заменив суммы документов на их отрицательные значения (и лимит также).
   NorthWind
 
49 - 24.03.21 - 19:00
(48) да, ветвей и границ здесь даст время близкое к полному перебору, непонятно как определять неоптимальность ветки.
А вот генетика тут может быть интересной. Фитнес-функция определяется легко - как раз дельта с итоговой суммой, чем меньше, тем лучше. И можно скрещивать сочетания доков, добиваясь хорошего результата.
   Михаил Козлов
 
50 - 24.03.21 - 19:39
(49) Генетика - буржуазная лженаука.
   Pepeega
 
51 - 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;
    выборка = Запрос.Выполнить().Выбрать();
    ПОКА выборка.Следующий() Цикл
        Если подобрано+выборка.Сумма<Объект.ТребуемаяСумма Тогда
            нов = Объект.Документы.Добавить();
            нов.РТиУ = выборка.Ссылка;
            нов.Сумма = выборка.Сумма;
            подобрано = подобрано+выборка.Сумма;
        ИначеЕсли (минВнеЛимитаРТиУ = НЕОПРЕДЕЛЕНО) ИЛИ (суммаМинРТиУ>выборка.Сумма) Тогда
            минВнеЛимитаРТиУ = выборка.Ссылка;
            суммаМинРТиУ = выборка.Сумма;
        КонецЕсли;
    КонецЦикла;
    // проверяем, не нужно ли включить не вошедший документ с минимальной суммой

    Если минВнеЛимитаРТиУ <> НЕОПРЕДЕЛЕНО И (подобрано+суммаМинРТиУ-Объект.ТребуемаяСумма<Объект.ТребуемаяСумма-подобрано) Тогда
        нов = Объект.Документы.Добавить();
        нов.РТиУ = минВнеЛимитаРТиУ;
        нов.Сумма = суммаМинРТиУ;
        подобрано = подобрано+суммаМинРТиУ;
    КонецЕсли;
КонецПроцедуры

&НаКлиенте
Процедура Подобрать(Команда)
    ПодобратьНаСервере();
КонецПроцедуры

Могу выслать обработку (мое мыло в профиле).
   Pepeega
 
53 - 02.04.21 - 09:50
(52) Спасибо за пример, помог в написании!


Список тем форума
 
ВНИМАНИЕ! Если вы потеряли окно ввода сообщения, нажмите Ctrl-F5 или Ctrl-R или кнопку "Обновить" в браузере.