我有一个 products 列表，其中包含出售它的 shops 列表。
{
'Book A': [ShopA, ShopB, ShopC],
'Book B': [ShopC, ShopD],
'Movie C': [ShopA, ShopB, ShopD, ShopE],
...
}
(各店价格不同)
每家商店也有运费。这是“按订单”的运输费用，与我的购物车中有多少物品无关。而且各个店铺也不同。
例如:如果我从 ShopA 购买“Book A”、从 ShopC 购买“Book B”和从 ShopA 购买“Movie C”，则结果价格为:
Book A price in ShopA + Book B price in ShopC + Movie C price in ShopA + ShopC shipping cost + ShopA shipping cost如果运输成本为零或者它是基于每个项目的并且是恒定的，那么我只会通过
price+shipping 字段对报价列表进行排序并从每个集合中获取第一个结果。我需要购买 所有 项目 一次 并找到最低价格 和 结果集。
我不太擅长优化算法和动态编程，所以我需要一个解决方案，或者只是向正确的方向点头。
最佳答案
对于这么少的物品，我有一个解决方案。它是动态的。
我们将迭代处理每家商店。在每一步，我们都会存储当前最优惠的价格，我们可以用它来覆盖商品的所有子集。一开始，除了价格的 infinity 空子集外，其余都是 0 。请注意，所有子集都是 2^Num_products 计数，但在您的情况下，这些只有大约 1000。
现在我们如何处理下一个跟随商店:考虑到您覆盖了这家商店的所有可能的产品子集(我的意思是商店实际上可以提供的子集)以及您已经观察到的商店覆盖的所有其余产品，因此提高覆盖每个子集的最低成本。这一步需要 2^Num_products*2^Num_products=4^Num_products ，仍然是大约一百万，这是可以承受的。您对每家商店都这样做，最后的答案是涵盖所有元素的成本。所提出的解决方案的整个复杂度是 4^Num_products * num_shops，大约有 5000 万，这很好。
请注意，这仍然是指数级的，这并不奇怪。感谢阿米特对 NP 难的令人难以置信的证明。
编辑 在伪代码中添加对算法的进一步解释:
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 是包含第一个、第二个和第四个元素的子集。因此，所有集合的迭代是
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 的所有子集。关于复杂性 - 请相信我。EDIT2 编辑中断条件。还让我详细说明集合
remaining 及其计算:正如 dmzkrsk 指出的伪代码提到从集合中删除，但您实际上可以只分配 remaining = set ^ covered_set(再次位操作)，以防使用位掩码来表示子集。关于algorithm - 购物车最小化算法，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/8891405/