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

2018-06-25 06:00:33

我有我想购买的n件物品的清单。（每个项目是不同的）

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

我知道k店铺和这些商店提供的物品清单。

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

保证我的名单上的每件商品至少在k家商店中的一家上有售。一旦您访问了一家商店，您可以购买1个或更多数量的您选择的物品。

问题我想尽量减少我需要访问的商店数量，以便购买我的清单上的所有商品。

我的解决方案1我使用蛮力DFS与memoization。这给出了最佳解决方案，但具有昂贵的复杂性（O（n！）），并且不适合我的要求。（有时候k和n最多可以达到300）

我的解决方案2我使用了一种贪婪的解决方案，在该解决方案中，我访问了商店，该商店在我的列表中提供了最大数量的商品购买物品，并从列表中删除所有这些物品。除非我的购物清单不是空的，否则我会再说一遍。（所有需要的物品都不买）

尽管解决方案2运行得非常快，但不幸的是，这种解决方案并不是最优的。

解决方案3使用Google搜索时，我发现了一个类似的问题，使用二分图和流程解决。（我仍然试图对此问题进行类比并检查此方法的适用性）

这是一个已知的问题吗？如果否，是否可以修改解决方案2以获得最佳解决方案？

我会很感激，如果你能帮助我解决这个问题，建议使用任何语言或任何方法或关键字（算法名称）等代码片段

这是一个已知的问题吗？

是的，这是一个设置封面问题（具体而言，它是未加权的品种）。已知它是NP完全的，所以你目前仅限于大概或太慢而不实际的解决方案。

链接地址: http://www.djcxy.com/p/70693.html