С такими маленькими предметами у меня есть решение. Это динамично.
Мы будем обрабатывать каждый магазин итеративно. На каждом шагу мы сохраняем текущую лучшую цену, с которой мы можем покрыть все подмножества элементов. В начале все они - infinity в цене, за исключением пустого подмножества, которое составляет 0. Обратите внимание, что все подмножества: 2^Num_products, но в вашем случае это всего около 1000.
Теперь, как мы обрабатываем следующий магазин: подумайте, что вы покрываете все возможные подмножества продуктов этим магазином (я имею в виду подмножество, которое магазин действительно может обеспечить), а все остальные продукты покрываются магазинами, которые вы уже наблюдали, тем самым улучшая минимальные затраты на покрытие всех подмножеств. Этот шаг занимает 2^Num_products*2^Num_products=4^Num_products, все еще около миллиона, который голый. Вы делаете это для каждого магазина, и в конце ответ - это стоимость покрытия всех элементов. Вся сложность предлагаемого решения составляет 4^Num_products * num_shops, что составляет около 50 миллионов, что хорошо.
Обратите внимание, что это все еще экспоненциально, и это неудивительно. Благодарим вас за невероятное доказательство NP.
EDIT Добавление дополнительного объяснения алгоритма в псевдокоде:
init:
cost[subset] = infi
cost[{}] = 0
for shop in shops
new_prices = costs.dup()
for set : subsets
for covered_set : all_subsets(set)
price = covered_set == {} ? 0 : delivery[shop]
remaining = set
for element : covered_set
if shop do not sale element
break for, choose next covered_set
price += el_price[element]
remaining.remove(element)
price += costs[remaining]
new_prices[set] = min(new_prices[set], price)
costs = new_prices
return costs[all]
Заметим, что здесь я использую наборы как индекс - это потому, что я на самом деле использовать битовую представление подмножеств, например, 1101 представляет собой подмножество, содержащее 1-го, 2-го и четвертого элементов. Таким образом, итерация всех наборов равна for (int i = 0; i < (1 << n); i++).
Существует и еще одна вещи: если вы хотите, чтобы цикл всех подмножеств подмножества S вы на самом деле можете сделать это быстрее, чем итерация всех подмножеств исходного набора и проверкой подмножеством является ли подмножество S. Если S также представлено с битовой маской bit_mask, это для цикла выполняет задание: for(int i = bit_mask; i > 0; i = (i - 1) & bitmask). Используя этот подход, вы уменьшаете сложность алгоритма до 3^Num_products * num_shops. Тем не менее, это немного сложнее понять, и вам, вероятно, потребуется написать вручную один пример, чтобы убедиться, что цикл, который я написал, фактически циклически выполняет все подмножества S. О сложности - просто поверьте мне.
EDIT2 Отредактировано состояние перерыва.также позвольте мне подробно рассказать о наборе remaining и его вычислении: как dmzkrsk указал, что псевдокод упоминает удаление из набора, но на самом деле вы можете просто назначить remaining = set^covered_set (снова операцию бит) в случае использования битмасков для представления подмножеств.
Можете ли вы дать некоторые оценки количества магазинов и продуктов, которые вам понадобятся для обработки. В настоящее время я придумал алгоритм, который хорошо работает только для очень небольшого количества продуктов, и у меня такое ощущение, что это не так ... –
5-10 предметов, 30-50 магазинов – dmzkrsk
Для любви к Богу, пожалуйста, реализуйте это. Это то, что я больше всего ненавижу в таких сайтах, как Amazon: не только заранее не знаю стоимость доставки, но я действительно не знаю, будут ли они отправляться на определенный адрес ** вообще **, пока я не получу проверку. – Groo