leafпочему то вспоминается задача о комовояжере ....
на такой задаче если ее решать в лоб не только запрос зависнет ...
тут надо отбрасывать заведомо не верные решения, сокращая число вариантов перебора+1
Как задача комивояжера, так и эта решается методом ветвей и границ .

ditochСтранно, но мне руководитель почему-то натоятельно советует делать запросом...Это комбинаторный алгоритм, а не метод реляционной алгебры. Причем, алгоритм РЕКУРРЕНТНЫЙ (использующий рекурсию). Обычным SQL-запросом его врядли удастся реализовать. Можно, конечно, написать хранимую процедуру... Но на рекуррентный вызов хранимых процедур на SQL-сервере наложены довольно жесткие ограничения, чтобы такое решение можно было бы рассматривать как работоспособное. Можно, конечно, попробовать преобразовать рекурсивный алгоритм в линейный циклический с реализаций "самопального" стека на неких вспомогательных таблицах. Но самый простой и очевидный метод - использовать рекурсивную процедуру 1С, вызывающую саму себя.

ditochКакие-то идеи?...Используется алгоритм рекурсивного "раскрашивания дерева" с отбрасыванием по дороге заведомо негодных ветвей (метод ветвей и границ).

При прохождении узла дерева с родительского уровня принимается множество коменклатур с количеством, формирующее промежуточное значение суммы ниже нижней границы заданного диапазона сумм. В каждом узле в двух циклах, вложенных друг в друга, производится попытка добавить еще один элемент в ранее сформированное множество. Один из циклов перебирает количество от 1 до имеющегося в наличии (поскольку речь идет о штуках), второй цикл делает попытку добавить еще одну номенклатуру. Какой из этих циклов в какой вкладывать - это уже дело хозяйское.

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

Если добавление еще одной штуки приводит к выходу за пределы верхней границы заданного диапазона суммы, то дальнейшее "раскрашивание дерева" прерывается с возвратом результата "уперлись в границу" (не прокатывает). Так отрабатывает метод ветвей и границ, предотвращая перебор большого количества заведомо бессмысленных комбинаций.

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

Если добавление еще одной штуки приводит к попаданию в диапазон, возвращается результат "решение найдено!", и дальнейший перебор вариантов прерывается. Не смотря на то, что решений может быть множество, алгоритм прерывает работу при нахождении первого же из них.

Если раскрашено всё дерево возможных вариантов, а решение не найдено, возвращается результат "решения нет!".

Обращаю внимание, что множество номенклатуры должно быть позиционно-независимым. То есть, множество номенклатур {2,3,5} = {3,2,5} = {5,2,3} = {5,3,2}. Они должны рассматриваться как одно и то же множество, и рассматриваться только один раз. Для того, чтобы реализовать позиционно-независимое множество, на каждом шаге рекурсии необходимо оперировать со упорядоченным множеством. Например, если мы отсортируем идентификаторы номенклатуры в порядке возрастания, и договоримся о том, что в множестве идентификаторы обязательно должны быть упорядочены по возрастанию, то любое из 4-х вариантов этих множеств будет приведено к одному-единственному {2,3,5}. И попадать в дальнейшую обработку (раскраску дерева) множества должны только после упорядочивания, исходя из концепции позиционной независимости.

Примерно так. Более детально - это уже нужно садиться и писать.
Данный алгоритм, конечно, требует некоторого опыта написания рекуррентных процедур. Потренируйтесь, для начала, на рекуррентной формуле N факториала:

Для N<0 результат="ошибка";
Для N<2 результат=1
Для остальных случаев N!=(N-1)!*N.

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

Успехов...

Программист 1сВот только когда товаров много (а их всегда много) и памяти не хватит и рекурсия загнется...Сомневаюсь, что для таких задач существует алгоритм, более оптимальный, нежели рекурсивный. Другое дело, что рекурсивный алгоритм может быть преобразован в циклический, если в нем самому реализовать некоторый эмулятор стека. В роли такого эмулятора может выступать массив, таблица, или что-то еще, в которой сохраняются параметры рекурсивного вызова и сообщается следующему шагу цикла, на каком уровне рекурсии мы находимся (типа "указатель стека").