从最少数量的商店购买购物清单中的所有商品

Question

我有一个清单，上面有我想买的n个项目。（每项不同）

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

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

我的解决方案1我使用暴力DFS和记忆。这给出了最优解，但具有昂贵的复杂性（O（N！））不符合我的要求。（k和n有时可达300）

我的解决方案2我使用了一个贪婪的解决方案，在这个解决方案中，我会访问在我的清单上提供最大数量商品的商店。购买项目，并从列表中删除所有这些项目。我重复这个，除非我的购物清单不是空的。（所需物品均不买）

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

在谷歌搜索Solution3时，我发现了一个类似的问题，这个问题是用二分图和流解决的。（我仍在尝试设置一个类比，并检查这种方法是否适用于我的问题）

Answer 1

这是一个已知的问题吗？

是的，这是一个集合覆盖问题（具体地说，它的未加权品种）。它已知是NP完全的，所以你目前只限于近似的或太慢而无法实用的解。