我有一个解决方案,可以处理如此少的项目。它是动态的。
我们将迭代地处理每个商店。在每个步骤中,我们存储当前最佳价格,以覆盖所有子项。一开始时,除了空子集(价格为0)以外,所有子集的价格都是无限的。请注意,所有子集的数量为2^Num_products,但在您的情况下只有大约1000个。
现在我们如何处理接下来要跟随的商店:考虑用这家商店涵盖产品的所有可能子集(我指商店实际提供的子集),并让所有其余的产品由你已经观察过的商店涵盖,从而改善覆盖每个子集的最小成本。这一步需要2^Num_products * 2^Num_products = 4^Num_products的时间,大约一百万次,可以承受。您对每个商店都要这样做,最终答案是覆盖所有元素的成本。所提出解决方案的整体复杂度为4^Num_products * num_shops,约为5000万,适合使用。
请注意,这仍然是指数级的,这不足为奇。感谢amit提供关于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的所有子集。关于复杂度-请相信我。
编辑2:修改了break条件,并让我详细说明一下集合
remaining
及其计算:正如
dmzkrsk
指出的那样,伪代码提到了从集合中删除,但是如果使用位掩码表示子集,则实际上可以将
remaining = set ^ covered_set
(再次是位操作)。