Есть список необходимых товаров (до 50 позиций). Каждый товар нужен по 1 штуке. Есть прайс, состоящий из номенклатуры-наборов. Т.е. номенклатура из прайса может состоять из одного или нескольких требуемых товаров. Один товар не встречается чаще чем в 10 номенклатурах. Необходимо собрать список номенклатуры, включающей весь список товаров (допускается попадание товара 2 и более раз) на минимальную сумму.

Так так. И как сделал?

(1) если бы сделал - не спрашивал :) Тупым перебором - лень, ищу легких путей

(2) А, так это вопрос :))
А то вопросительных знаков просто не видно :))

(3) Думал слова "подскажите" в заголовке будет достаточно

(4) Схалтурить думал? :))

Алгоритма ускоряющего подбор одного списка товаров нет.

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

А откуда такая задача-то?

Делаешь полный перебор сочетаний номенклатур (пересечений множеств товаров) так чтобы создать/выбрать более крупные наборы включающие минимум пересекающихся товаров.

Затем входной список товаров банально в списке товаров, где лучше соответствие то и берешь и добиваешь одиночными номенклатурами или 2-ми, 3-ми и т.д. как получится.

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

(9) Тьфу у тебя минимизация по отдельному параметру - цене а не кол-ву.

+(9) не два парных а две пары. Типа печенька+конфетка = рупь и яблоко +банан = рупь. А все четыре вместе - 3 рубля.

(7) поликлиника - профосмотры.

Куча вложенных циклов
Первый по номенклатуре, в которой есть товар1
Второй по номенклатуре, в которой есть товар2
И так далее
В случае, если товарN уже есть в набранных товарах, то пропускаем

(13) я же в 2 сказал - перебором можно, хотел че нить из высшей математики, счас так модно :)

(13) Перебором "до 50 позиций" будет пипец как долго.

(14) Так тут только перебор

(15) Ну таки да, а что делать?

(15) надеялся что нить типа "рюкзака" всплывет. Просто основы анализа так давно проходил... мимо...

+(17) 10^50 по максимуму так-то, да :))

(12) номенклатура это врачи?

Попробуй для начала деревья из номенклатур-наборов построить и глянуть ветвистость.

"Типа печенька+конфетка = рупь и яблоко +банан = рупь. А все четыре вместе - 3 рубля."

"печенька+конфетка" и "яблоко+банан" входят в "все четыре вместе" и т.д.

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

(20) Думаешь цель минимальным кол-вом врачей закрыть максимум специальностей/услуг и как можно дешевле?

(20) нет. Анализы. Врач - всегда один в номенклатуре

Минимизация по затратам на зп врачей ))

(23) они что какими-то комплексами идут? 50 анализов? Вы космонавтов обследуете?

(24) Если бы - глупое пожелание заказчика минимизировать счет клиенту :)

А может просто прайс лист заставить поменять? На нормальный без наборов а одиночные только.

(26) Добавить в прайс комплекс из 50 анализов не предлагали?

(25) Ты не поверишь какие требования у минздрава к нянечкам в детсадах :)

Кстати задачка идеальна для тупого параллельного перебора - на GPU (OpenCL или CUDA).

(30)+ Любая новая видяшка (из ныне продающихся) уже умеет из коробки OpenCL (почти все) или CUDA (nvidia)

(18) Вот тут вся математика https://ru.wikipedia.org/wiki/Целочисленное_программирование

Хотя..., может как-то так...

Берем набор из десяти наиболее дешевых товаров, где в первой номенклатуре есть товар1, во-второй есть товар2 и т. д.
Фиксируем текущую минимальную стоимость

Пробуем с помощью вложенных циклов убирать товары, после убирания которых в остальных товарах все-равно полный комплект
В случае удачи фиксируем новую текущую минимальную стоимость, если она меньше текущей

После этого пробуем перебор с отсечением ветки в случае, если новая стоимость выше или равна минимальной

Да, это вам не задачки 1Сергея для начальной школы :))

(32)+ Если товар попадает в набор точно один или ноль раз, то это задача 0-1 ЦЛП. Немного проще, но не сильно.
Задача NP-полная, алгоритмов для нее масса. И точные, и эвристические. Всё есть в Яндексе.

https://ru.wikipedia.org/wiki/Задача_о_покрытии_множества

https://ru.wikipedia.org/wiki/Упаковка_множеств

https://ru.wikipedia.org/wiki/Задача_о_назначении_минимального_количества_исполнителей

"На классах задач, где n или m ограничены константой, задача за полиномиальное время решается методами полного перебора."

Хочешь точное решение - только полный перебор ))

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

(28) Присоединяюсь. И повторений не будет: как-то странно будет выглядеть счет, где придется 2 раза сдавать кал.

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

(41) Тебе сложно штоль?

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

(43) В смысле алгоритм найти/придумать или кал сдать?
После 5-ого курса были военные лагеря. Так вот один однокашник впервые сходил по большому через 3 недели.
Так что разные бывают ситуации.

похоже на задачку c sql-ex.ru

Может быть попробовать другую постановку задачи:
определить стоимость каждого анализа с условием, что сумма
анализов входящих в набор = стоимости набора (из прайса) и сумма стоимостей всех анализов - минимальна.
Искомые переменные: Xi - стоимость i-того анализа
Ограничения:
1. Xi>=0
2. СУММА(Xi по входящим в набор j) = Цj (цена набора из прайса) (для всех j)
3. СУММА(Xi) -> MIN

Это задача линейного программирования. Реализация симплекса метода на 1С есть - могу выслать.
Задача специальной структуры - может можно свести к потоку в сети.