Говорил мне мой преподаватель - учись... но это было давно...
Задачка вроде бы простая, но в рабочую субботу мозги уже не варят. Есть список необходимых товаров, есть наборы в которых лежат эти товары. Стоимость набора равна стоимости товара в этом наборе. В разных наборах товары могут пересекаться. Необходимо выбрать наборы, что бы все товары требуемого списка попадали как минимум по одному разу на минимальную общую сумму. Понятно, что жадным алгоритмом или полным перебором это решается, есть что-то пооптимальнее?

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

Отсортируй по возрастанию цены наборы. И перебирай с выходом, как только найдешь свою минималку

Пооптимальней (пока нет квантовых компов) только алгоритмы с хорошим распераллеливанием
В много потоков одновременно перебором искать

(3)+ Много потоков я подразумеваю не обычные CPU до сотни ядер
А GPGPU на видеокартах в тысячи одновременно

(0) А для чего это нужно? В реальной жизни эта задача как выглядит?

(5) Похоже на подбор подтверждающих документов по списку встречающихся позиций при выборочной проверке

ээээ.. я чего-то не понял...
"есть наборы" - то есть уже сформированные/зафиксированные. число таких наборов явно небольшое. наборы генерить не надо.
Сформировали набор из списка требуемых товаров. И даже тупо перебрать наборы и сравнить с требуемым типа как в (3), при чем здесь отимизационные задачи...?

(0) Пример на бумаге приведите.

(5) (8) Пример простой - сборка профиля пользователя из ролей в 1С на определенные действия. Например нужно дать права на ввод 3 документов => надо найти роли с правом редактирования доков и просмотр справочников. Подбирать вручную...

+9 Полные права не предлагать :)

Вы там скоро совсем рёхнитесь со своей безопасностью, кому какие права давать на каждый пук.
Всё равно, если приспичит, то прога купят или запугают, и ВСЮ инфу получат.
Когда коту делать нечего...

(9) Когда "нужно дать права на ввод 3 документов" - создают новую роль и дают ее
Если нет стандартных/типовых ролей только на эти 3 документа

Попробуем формализовать задачу:
Xi = {0,1} - искомые переменные. Xi=1, если i-тый набор войдет в решение (можно считать Xi просто целыми, но ясно, что включать более 1 набора в решение нет смысла);
Aij - количество j-того товара в i-том наборе (если в наборе количество товара не более 1, тогда Aij либо 1 либо 0);
Cj - стоимость j-того товара.
Условие, что все товары войдут в выбор:
СУММА(по i)Aij*Xi>=1 (для всех j)
Критерий:
стоимость i-того набора = СУММА(по j)Aij*Cj - это число, обозначим его Bi
СУММА(по i)Xi*Bi -> MIN
Формально, это похоже на многомерный ранец (частный случай). Можно поискать что-то на эту тему.
Возможно неплохо себя покажет схема ветвей и границ неявного перебора, в которой релаксированной задачей будет выступать задача линейного программирования.
Можно попробовать (благо выходные) какой-либо вариант жадного алгоритма.
Например, упорядочить наборы по отношению числа нужных товаров к стоимости набора. Выбрать минимальный. Пересчитать число оставшихся нужных/Bi, выбрать второй и т.д.

Поищите про задачу поиска минимального покрывающего множества (например https://www.geeksforgeeks.org/greedy-approximate-algorithm-for-set-cover-problem/)

Вот еще: https://www.bibliofond.ru/view.aspx?id=896346
Пишут, что это NP-полная задача.

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

(0) распиши нормально задачу, ответ тут на поверхности

Считаем Сумму набора и к во позиций. Сразу откидываем все наборы где позиций меньше и те у которых сумма меньше. Дальше сортируем по сумме и перебор. Если в наборе 10 позиций. в проверяемом 12
Мы проверили 3 позиции и не нашил их, дальше набор можно не проверять прерываем цикл. Как только в наборе остается меньше позиций чем нам нужно еще найти отбрасываем набор как неподходящий.

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

Стоимость нашего набора 3000. проверяемого 4000. Первая позиция стоит 1500 проверили ее она не вошла в наш набор остальные позиции можно не проверять. Полный набор точно не соберем так как осталось 2500, а ищем 3000.

(18)-(20) wiki:Задача_о_покрытии_множества

(21) И ??? От туда же "На классах задач, где "n" или "m" ограничены константой, задача за полиномиальное время решается методами полного перебора."
В реальной жизни решение можно ускорить. Проиндексировав множества по дополнительным характеристикам.
Например по весу или объему откинув дополнительно и те наборы которые меньше или легче. применив сортировку внутри множеств делать не полный перебор, а частичный.

Тс уже ливнул, а вы тут стараетесь