Добрый день, возникла проблема, понадобилось написать алгоритм, который будет искать документы с более подходящими ценами, то-есть пользователь допустим вводит сумму 10 тысяч, ему из всех документов выбираются документы те, у которых общая сумма будет 10 тысяч или близкая к этой сумме, но не больше, полдня уже ломаю голову и ничего не приходит на ум, если кто-то сталкивался с проблемой буду благодарен за помощь

(0) документы одного типа? Что будет правильно вернуть 2 документа по 5тыс или 1 док на 10тыс?

(0) все комбинации документов?

А вы про "не могут написать функцию, которая выводит строку в обратном порядке"...

(0) может быть куча решений

Надо накладывать какой то критерий оптимальности(почему один набор документов лучше другого набора с такой же суммой) - и получается задача о рюкзаке. Способы решения гуглятся.

(1) Да, документы одного типа, расходная накладная
(2) перебрать все документы и найти лучшую цену документов, исходя из той, которую ввел пользователь

(3) ну, если вы про "перебрать документы по убыванию цены" , то это не совсем правильный подход к такой задаче

(5) масло масляное.Если даже критерии не можешь узнать у заказчика

(4) да вот я погуглил решения и что-то как-то не совсем понимаю, как мне перебрать эти кучи документом и найти оптимальные документы, если я допустим перебрал все документы, как я узнаю, что допустим 3 документа 900р + 5000р + 4000р лучше, чем остальные, куда сохранять все наборы документов?

(7) Заказчик указал, что ему нужно, чтобы он вводил в поле цену "Допустим 10000р", и из всех документов которые были за последний месяц, ему отобрались документы с более подходящей суммой цен = 10000р

(9) Ноль он дал,дальше узнавай подробности [ с более подходящей суммой цен = 10000р]

(9) если у тебя 1000 вариантов наборов документов и у каждого сумма = 10000, какой выбирать?

перебрать все документы не составляет труда, возникла именно проблема с построением, допустим есть всего 5 документов за месяц, сумма всех документов 18000р, первые 3 допустим общую сумму 9500 имеют, а вот другие 2 имеют общую сумму 9990р, как я узнаю, что второй вариант лучше, чем первый, мне же куда-то его сохранить нужно, а если таких документов несколько тысяч?

(11) тут не играет роль, какие документы увидит пользователь, они будут отсортированы по дате, сейчас проблема всей задачи, это правильный алгоритм, который будет находить лучшею цену

(12) ну так сохраняй, в чём проблема-то?

(14) а так можно было??? ))

(15) Не-а :)

(14) не совсем понимаю куда, вот в чем проблема, ну окей, нашел я 3 документа с общей суммой 9000р, сохраняю их в массив, их же нужно отделить как-то, чтобы сравнить потом набор разных документов

(13) Слушай, ну по конкретной реализации алгоритма - тут уж поднапряги мозги. Как говорят герои - "никто, кроме тебя".

(18) Нормальные герои всегда идут в обход (С)

(17) Новый Структура(НомерИтерации, МассивДокументов, Сумма)

(18) Тут вы правы, но на самом деле не лезет в голову момент сохранения разных наборов документов, только для этого сюда написал.

Думаю, что нужно сходить на обед и в голову придут варианты, все равно спасибо, кто откликнулся!

(9) "ему отобрались документы с более подходящей суммой цен = 10000р"

Ты в 5 раз твердишь одно и тоже бессмысленное сочетание "с наиболее подходящей". Этот словесный критерий надо формализовать, положить на язык математики
Нихрена не понятно что заказчик имеет ввиду под "наиболее подходящим"

(22) Видимо объяснил и вправду не совсем корректно, сам имею больше информации, как и писал выше, если пользователь вводит сумму 10000р, после обхода рекурсией всех вариантов, у нас допустим в массиве получается 5 записей, 1) 8300р. 2) 9000р. 3)7800р. 4) 9800р. 5) 10000р. и мы должны будем указать вывести те документы, которые находятся в 5й записи, если бы не было 5й записи, то тогда 4, потому что она самая близкая к 10000р(введённая сумма пользователем)

(20) спасибо, как вариант подумать в эту сторону

(23) я конечно очень старомодный, но может не хранить все наборы, тупо на каждой итерации сравнивать сумму нового набора с суммой сохраненного ранее и если новый набор оптимальнее, то сохранять его вместо старого?

(23) Запросом отобрать док-ты, у которых сумма меньше введенной (параметр + условие).
Результат запроса упорядочить по возрастанию суммы.
Вывести первую запись результата запроса.

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

лет 15 назад писал какую-то тупую хрень по тупым алгоритмам с тупыми недоработками. тупо работала.
https://infostart.ru/public/14526/

(25) с этой стороны хотел подойти, уже даже появилось полное решение, но на половине пути реализации, я понял, что первая "пачка" документов может быть 9000р, вторая 10000р, третья 8500р, четвёртая 9200р, если просто проверять, лучше наше значение чем последнее сохранённое или нет, то те самые 9000р и 10000р уже будут не в нашей видимости и мы о них не будем знать

ЦелеваяСумма=1000000;
    СуммаКСписанию=ЦелеваяСумма;
    МассивДокументов=Новый Массив;
    Пока Истина Цикл
        Запрос=Новый Запрос;
        Запрос.Текст=
        "ВЫБРАТЬ ПЕРВЫЕ 1
        |    РеализацияТоваровУслуг.Ссылка КАК Ссылка,
        |    РеализацияТоваровУслуг.СуммаДокумента КАК СуммаДокумента
        |ИЗ
        |    Документ.РеализацияТоваровУслуг КАК РеализацияТоваровУслуг
        |ГДЕ
        |    РеализацияТоваровУслуг.СуммаДокумента <= &СуммаКСписанию
        |
        |УПОРЯДОЧИТЬ ПО
        |    СуммаДокумента УБЫВ";
        Запрос.УстановитьПараметр("СуммаКСписанию",СуммаКСписанию);
        Выборка=Запрос.Выполнить().Выбрать();
        Если Выборка.Количество()=0 Тогда
            Прервать;
        КонецЕсли;
        Выборка.Следующий();
        Если Выборка.СуммаДокумента<=0 Тогда
            Прервать;
        КонецЕсли;
        
        СуммаКСписанию=СуммаКСписанию-Выборка.СуммаДокумента;
        МассивДокументов.Добавить(Выборка.Ссылка);
        Если СуммаКСписанию<=0 Тогда
            Прервать;
        КонецЕсли;        
    КонецЦикла;

(26) Тоже как вариант, но сумма может быть не 10000р, а больше, все равно придётся прибегать к алгоритму, который будет из всех полученных документом искать какую-то наилучшую общую сумму "пачки" документов

Запрос плох, в промсистеме нужно рассмотреть добавления индеска по сумме.

(29) с чего вдруг ?
Первая пачка 9000, вторая 8500, ее не храним, сравниваем с первой. Третья 10000, не храним первую ибо третья лучше. Т.о. всегда сравниваем с лучшей пачкой

(30) Спасибо за пример, уже хотел прибегнуть к чему-то похожему, но стараюсь отказаться от запросов в цикле, хоть мы и выбираем 1 документ всего, но всё же, но вариант вполне рабочий, спасибо за потраченное время!
я тут подумал, что можно же один раз получить все документы, оставить только нужные и уже дальше циклом перебирать по аналогии

(33) Не сразу понял такой вариант, но да, если такой вариант тоже вполне подходит для решения.

Спасибо всем кто откликнулся, думаю что-то придумать на свежую голову получится!

(0) задача о рюкзаке, что ли?

ну да, она. у вас вместимость рюкзака это сумма на которую набирать, а документы - предметы.

(0) Задача о рюкзаке.

рюкзак еще не предлагали?

(39) лучше деньгами....)

да, подобие задачи о рюкзаке
(37) это понятно, осталось только с алгоритмом закончить :)

(39) Пока нет. Думаю, надо предложить, а то никто так и не вспомнит.

а рассматривали применить что-нибудь от рюкзака? Метод ветвей и границ, динамическое программирование, еще что-нибудь? Там же куча методов, все они описаны, и, насколько я помню, не сильно сложны. Первый курс института.

(43) Да, решаю с помощью динамического программирования

(43) Не торопи события. Сначала у ТС запрос, генерирующий все варианты, должен колом встать.
Потом он задумается о других методах.

(0) задача рюкзака отлично решается "Динамическим программированием" из высшей математики
https://ru.wikipedia.org/wiki/Динамическое_программирование

https://ru.wikipedia.org/wiki/Задача_о_рюкзаке

(44) опоздал я с ответом))

(41) Ваша задача немного отличается от рюкзака: нужно подобрать не максимальную сумму (без превышения лимита), а наименее отличающуюся от него.
Для рюкзака неплохо работает жадный алгоритм:
- упорядочить документы по убыванию суммы;
- выбирать документы в этом порядке. Если текущая сумма + сумма документа укладывается в лимит, добавить документ в массив отобранных.
Может быть имеет смысл поискать более хитрый (чем жадный) алгоритм для рюкзака. Можно попробовать и метод динамического программирования, только нужно иметь в виду, что рюкзак "почти" полная переборная задача, и метод динамического программирования, вообще говоря, может привести к перебору. Метод ветвей и границ в рюкзаке не сработает: не будет эффективного отсечения.
Я бы попробовал жадным алгоритмом решить 2 задачи о рюкзаке. Одна - на максимум с меньше лимита, вторая - на минимум с больше лимита. Вторую можно свести к первой заменив суммы документов на их отрицательные значения (и лимит также).

(48) да, ветвей и границ здесь даст время близкое к полному перебору, непонятно как определять неоптимальность ветки.
А вот генетика тут может быть интересной. Фитнес-функция определяется легко - как раз дельта с итоговой суммой, чем меньше, тем лучше. И можно скрещивать сочетания доков, добиваясь хорошего результата.

(49) Генетика - буржуазная лженаука.

В общем вот что получилось, но не совсем корректно работает, потому что у меня все массивы имею значения 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]);
    КонецЕсли;

Разбираться не стал. Вот вариант жадного алгоритма (для УФ). Предполагается, что все суммы в одной валюте.
&НаСервере
Процедура ПодобратьНаСервере()
    Объект.Документы.Очистить();
    Запрос = Новый Запрос;
    Запрос.Текст =
    "ВЫБРАТЬ
    |    РТиУ.Ссылка КАК Ссылка,
    |    РТиУ.СуммаДокумента КАК Сумма
    |ИЗ Документ.РеализацияТоваровУслуг КАК РТиУ
    |ГДЕ РТиУ.Дата МЕЖДУ &датаНач И &датаКон И РТиУ.СуммаДокумента<=&максСумма
    |УПОРЯДОЧИТЬ ПО Сумма УБЫВ";
    Запрос.УстановитьПараметр("датаНач", Объект.датаНач);
    Запрос.УстановитьПараметр("датаКон", Объект.датаКон);
    Запрос.УстановитьПараметр("максСумма", Объект.ТребуемаяСумма);
    минВнеЛимитаРТиУ = НЕОПРЕДЕЛЕНО; суммаМинРТиУ = 0; // для не вошедшего документа с минимальной суммой
    подобрано = 0;
    выборка = Запрос.Выполнить().Выбрать();
    ПОКА выборка.Следующий() Цикл
        Если подобрано+выборка.Сумма<Объект.ТребуемаяСумма Тогда
            нов = Объект.Документы.Добавить();
            нов.РТиУ = выборка.Ссылка;
            нов.Сумма = выборка.Сумма;
            подобрано = подобрано+выборка.Сумма;
        ИначеЕсли (минВнеЛимитаРТиУ = НЕОПРЕДЕЛЕНО) ИЛИ (суммаМинРТиУ>выборка.Сумма) Тогда
            минВнеЛимитаРТиУ = выборка.Ссылка;
            суммаМинРТиУ = выборка.Сумма;
        КонецЕсли;
    КонецЦикла;
    // проверяем, не нужно ли включить не вошедший документ с минимальной суммой
    Если минВнеЛимитаРТиУ <> НЕОПРЕДЕЛЕНО И (подобрано+суммаМинРТиУ-Объект.ТребуемаяСумма<Объект.ТребуемаяСумма-подобрано) Тогда
        нов = Объект.Документы.Добавить();
        нов.РТиУ = минВнеЛимитаРТиУ;
        нов.Сумма = суммаМинРТиУ;
        подобрано = подобрано+суммаМинРТиУ;
    КонецЕсли;
КонецПроцедуры

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

Могу выслать обработку (мое мыло в профиле).

(52) Спасибо за пример, помог в написании!