我有一个产品列表，其中包含了销售它的商店列表。
{
'Book A': [ShopA, ShopB, ShopC],
'Book B': [ShopC, ShopD],
'Movie C': [ShopA, ShopB, ShopD, ShopE],
...
}
（价格因商店而异）
每家商店还有一笔运费。这是一笔“按订单”计算的运费，无论购物车中有多少件商品都不会改变。而且，这个费用也因商店而异。
例如：如果我从ShopA购买“A书”，从ShopC购买“B书”，并从ShopA购买“C电影”，那么最终价格为：ShopA中A书的价格 + ShopC中B书的价格 + ShopA中C电影的价格 + ShopC的运费 + ShopA的运费
如果运费为零或按项计费且保持不变，则我只需按price+shipping字段对报价列表进行排序并从每个集合中获取第一个结果。
我需要购买全部商品一次性购买，并找到最小价格和对应的商品集。
我不太擅长优化算法和动态规划，所以我需要一个解决方案或者指引正确的方向。
S1，S2，...，Sn和一个数字k：选择大小为k的集合S，使得对于每个Si，都有一个元素s在S中，使得s在Si中。[另一种定义：每个Si和S之间的交集不为空]。
约简：
给定一个Hitting Set实例，形式为(S1，...，Sn，k)，创建该问题的一个实例：
All books cost nothing. In order to buy from each store you pay 1.
The book i is sold by each store denoted in Si, minimal price for this instance is k.
证明：
击中集合 -> 这个问题：假设在大小为k的(S1,...,Sn)的最小击中集中存在一个击中集S。通过从S中的每个商店购买，我们可以以成本k购买所有书籍，因为书籍在我们的构建中不花费任何费用，我们购买了所有书籍，并支付了来自商店的订购费用恰好为k，因此总价格为k。
这个问题 -> 击中集合：假设问题的定价为k。然后，根据问题的构建，由于书籍不花费任何费用，我们需要在k个不同的商店购买所有书籍。让这些商店为S。从问题的构建中，S是(S1,...,Sn)的一个击中集。
证毕。
结论:
因此，这个问题与Hitting Set Problem同样难度，目前没有已知的多项式解决方案，所以-如果你想要最优解，你最好选择指数级别的解决方案，比如回溯算法 [检查所有可能性，并返回最小的解决方案]。
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]
for (int i = 0; i < (1 << n); i++)。S的所有子集，可以比迭代初始集合的所有子集并检查子集是否是S的子集更快地完成此操作。如果S也用位掩码 bit_mask 表示，则此 for 循环执行此任务：for(int i = bit_mask; i > 0; i = (i - 1) & bitmask)。使用这种方法，您可以将算法复杂度降低到3^Num_products * num_shops。但是，这有点难以理解，您可能需要手写一个示例，以确保我编写的循环实际上循环遍历了S的所有子集。关于复杂度-请相信我。remaining 及其计算：正如dmzkrsk指出的那样，伪代码提到了从集合中删除，但是如果使用位掩码表示子集，则实际上可以将 remaining = set ^ covered_set （再次是位操作）。