algorithm - 从最少数量的商店中购买购物 list 中的所有商品

Question

我有一个我想买的 n 件元素的 list 。 (每个项目都是不同的)

list = {item1, item2, item3 .... itemn}

我知道 k 家商店以及这些商店的可用商品列表。

shop1 = {item3, item5, item6 ...}
shop2 = {item1, item5, item8 ...}
...
shopk = {item1, item6, item8 ...}

保证我列表中的每件商品在 k 家商店中至少有 1 家有售。访问商店后，您可以购买 1 件或多件您选择的商品。

问题我想尽量减少购买 list 上所有商品所需的商店数量。

我的解决方案 1 我使用带内存的暴力 DFS。这提供了最佳解决方案，但具有昂贵的复杂性(O(n!))并且不符合我的要求。 (k和n有时可以达到300)

我的解决方案 2 我使用了一个贪婪的解决方案，在该解决方案中，我访问了在我的列表中提供最大数量商品的商店。购买元素，并从列表中删除所有这些元素。我重复一遍，除非我的购物 list 不为空。 (所需元素全部未购买)

虽然解决方案 2 运行得非常快，但不幸的是，这个解决方案并不是最优的。

研究 Solution3 在谷歌搜索时，我发现了一个类似的问题，该问题已使用二分图和流解决。 (我仍在尝试设置类比并检查这种方法对我的问题的适用性)

这是一个已知问题吗？如果不是，是否可以修改解2得到最优解？

如果你能通过建议一些任何语言或任何方法或关键字(算法名称)等的代码片段来帮助我解决这个问题，我将不胜感激

Answer 1

Is this a known problem?

是的，这是一个Set Cover Problem (具体来说，它是未加权的品种)。已知它是 NP 完全的，因此您目前只能使用近似或太慢而不实用的解决方案。