Buy all items of a shopping list from minimum number of shops

I have a list of n items that I want to buy. (Each item is distinct)

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

I know k shops and list of items available on these shops.

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

It is guaranteed that each item on my list is available on at least 1 of the k shops. Once you visit a shop, you can buy 1 or more number of items of your choice.

Question I want to minimize the number of shops I need to visit to buy all items on my list.

My Solution1 I used Brute force DFS with memoization. This gives optimal solution but has expensive complexity(O(n!)) and not feasible for my requirement. (k and n can reach up to 300 sometimes)

My Solution2 I used a greedy solution in which I visit the shop that offers maximum number of items on my list. Buy items, and remove all those items from list. I repeat this unless my shopping list is not empty. (All required items are not bought)

Although solution 2 runs very fast Unfortunately this solution is not optimal.

Working on Solution3 While googling, I found a similar problem that was solved using bipartite graph and flow. (I am still trying to set an analogy and check applicability of this approach for my problem)

Is this a known problem? If no, Is it possible to modify solution 2 to get optimal solution?

I would thankful if you can help me solving this problem by suggesting some code snippet in any language or any approach or keyword(algorithm name) etc

---

Is this a known problem?

Yes, this is a Set Cover Problem (specifically, its unweighted variety). It is known to be NP-complete, so you are currently limited to solutions that are either approximate or too slow to be practical.

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

上一篇: 匹配与完美匹配的区别

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